一种排序快速排序算法的实现
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); } }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。