c语言中的快排及优化

1万 · 2023-4-24 12:00

快速排序被称为最常用的排序，他的主要思想是，利用某个基准数，将其比基准数大或小分别放在基准数的两边，让后在两边在找一个基准数，再次进行相同的操作，直到最后只有一位时，排序就完成了。快排之所以较快，是因为其是基于二分法，它的交换是跳跃式的。

下面是基本的快排的代码：
对于快速排序，它还可以继续进行优化，在基准数的选定上，我们可以选取中间的数进行排序，这样可以缩短一些时间。代码如下：

1万 · 2023-5-10 13:54

快速排序(Quicksort)是对冒泡排序的一种改进。快速排序由C. A. R. Hoare在1962年提出

只看该作者 · 2023-5-10 14:19

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

只看该作者 · 2023-5-10 14:45

随机化快排是快速排序的最坏情况基于每次划分对主元的选择

只看该作者 · 2023-5-10 15:06

平衡快排每次尽可能地选择一个能够代表中值的元素作为关键数据，然后遵循普通快排的原则进行比较、替换和递归

1万 · 2023-5-10 16:08

迭代法

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[p++]為push,r[--p]為pop且取得元素

Ranger[len];

intp=0;

r[p++]=new_Range(0,len-1);

while(p){

Rangerange=r[--p];

if(range.start>=range.end)

continue;

intmid=arr[range.end];

intleft=range.start,right=range.end-1;

while(left<right){

while(arr[left]<mid&&left<right)

left++;

while(arr[right]>=mid&&left<right)

right--;

swap(&arr[left],&arr[right]);

}

if(arr[left]>=arr[range.end])

swap(&arr[left],&arr[range.end]);

else

left++;

r[p++]=new_Range(range.start,left-1);

r[p++]=new_Range(left+1,range.end);}

}

只看该作者 · 2023-5-10 16:30

快速排序算法的性能作在最坏情况和平均情况下是不同的

c语言中的快排及优化

相关下载

相关帖子

十世金身

技术领袖奖章

坚毅之洋流

荣誉元老奖章