c语言中的快排及优化
快速排序被称为最常用的排序，他的主要思想是，利用某个基准数，将其比基准数大或小分别放在基准数的两边，让后在两边在找一个基准数，再次进行相同的操作，直到最后只有一位时，排序就完成了。快排之所以较快，是因为其是基于二分法，它的交换是跳跃式的。下面是基本的快排的代码：
对于快速排序，它还可以继续进行优化，在基准数的选定上，我们可以选取中间的数进行排序，这样可以缩短一些时间。代码如下：
快速排序(Quicksort)是对冒泡排序的一种改进。快速排序由C. A. R. Hoare在1962年提出 其基本思想是:通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列 随机化快排是快速排序的最坏情况基于每次划分对主元的选择 平衡快排每次尽可能地选择一个能够代表中值的元素作为关键数据，然后遵循普通快排的原则进行比较、替换和递归 迭代法
typedefstruct_Range{
intstart,end;
}Range;
Rangenew_Range(ints,inte){
Ranger;
r.start=s;
r.end=e;
returnr;
}
voidswap(int*x,int*y){
intt=*x;
*x=*y;
*y=t;
}
voidquick_sort(intarr[],constintlen){
if(len<=0)
return;//避免len等於負值時宣告堆疊陣列當機
//r[]模擬堆疊,p為數量,r為push,r[--p]為pop且取得元素
Ranger;
intp=0;
r=new_Range(0,len-1);
while(p){
Rangerange=r[--p];
if(range.start>=range.end)
continue;
intmid=arr;
intleft=range.start,right=range.end-1;
while(left<right){
while(arr<mid&&left<right)
left++;
while(arr>=mid&&left<right)
right--;
swap(&arr,&arr);
}
if(arr>=arr)
swap(&arr,&arr);
else
left++;
r=new_Range(range.start,left-1);
r=new_Range(left+1,range.end);}
} 快速排序算法的性能作在最坏情况和平均情况下是不同的
页:
[1]