一种排序快速排序算法的实现

1.快速排序的思想:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。

2.实现:首先写一个将数组分割成两块的函数int Partion(int arr[],int len);返回值为分割后的中间点。该函数以数组第一个数为分割标志。

 1 int partion(int arr[],int len){
 2     int m=0;
 3     int flag=arr[m];
 4     int now=0;
 5     if(len==1)
 6     return 0;
 9     for(int i=0;i<len;i++)
10     {
11        if(arr[i]<flag)
12        {
13         swap(arr[i],arr[m]);
14         m++;
15         now =i;
16        }
17     }
19     return m;
20     }

一次调用后数组会分成两个部分,左边部分全部小于分割标志,右边部分全部大于分割标志。

2.递归对左部分和右部分进行排序。

int qsort(int arr[],int len)
{
    if(len==1)
        return 0;
    int re=partion(arr,len);
    if(re==0)
    {
         qsort(&arr[re+1],len-re-1);
         return 0;
    }
    else{
    qsort(arr,re);
    qsort(&arr[re],len-re);
    }
}

 

郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。