学步园

之前总以为自己已经掌握了快速排序，可是眼高手低，没有好好研究一下它是否是稳定的排序，以及涉及重复元素等问题，最近用到时总是出现小的bug，于是又潜心翻看《算法导论》，经过测试，写出一个正确的快速排序算法。

写正确关键在于paration函数：

(1)如果s<=k<=i,则有a[k]<=m（中枢元素）

(2)如果i+1<=k<=j-1,则有a[i]>m

(3)如果k=e,则有a[k]=x

变量s和e分别表示数组a的起始和结尾元素，i用于跟踪j，直到遇到>中枢元素m的值，此时a[i+1]>m，等待下次（如果存在）遇到<=中枢元素m的知，然后交换。

注意：在paration()函数中选择随机中枢元素时，必须基于当前s值（即在当前s上加上随机值）。

1 #include <stdio.h><br /> 2 #include <stdlib.h><br /> 3 #include <time.h><br /> 4 void quite_sort(int *,int,int);<br /> 5 int paration(int*,int,int);<br /> 6 void print(int*,int );<br /> 7 void swap(int*,int* );<br /> 8 int main()<br /> 9 {<br /> 10 int a[]={1,2,5,3,2,1,7,4};<br /> 11 quite_sort(a,0,7);<br /> 12 print(a,8);<br /> 13<br /> 14 //int b[]={9,9,8,8,7,7};<br /> 15 //quite_sort(b,0,5);<br /> 16 //print(b,6);<br /> 17<br /> 18 //int c[]={2,2,2,2};<br /> 19 //quite_sort(c,0,3);<br /> 20 //print(c,4);<br /> 21<br /> 22 }<br /> 23 void print(int *a,int len)<br /> 24 {<br /> 25 int i = 0;<br /> 26 for(;i<len;i++)<br /> 27 printf("%d ",a[i]);<br /> 28 printf("/n");<br /> 29 }<br /> 30 void quite_sort(int *a,int s,int e)<br /> 31 {<br /> 32 if(s<e)<br /> 33 {<br /> 34 int p = paration(a,s,e);<br /> 35 quite_sort(a,s,p-1);<br /> 36 quite_sort(a,p+1,e);<br /> 37 }<br /> 38 }<br /> 39 int paration(int *a,int s,int e)<br /> 40 {<br /> 41 int l = e-s+1;<br /> 42 srand(time(NULL));<br /> 43 int r = rand()%l+s;<br /> 44 swap(&a[r],&a[e]);<br /> 45 int m = a[e];<br /> 46 printf("aaa%d /n",r);<br /> 47<br /> 48 int i =s-1,j = s;<br /> 49 while(j<e)<br /> 50 {<br /> 51 if(a[j]<=m)<br /> 52 {<br /> 53 i++;<br /> 54 swap(&a[i],&a[j]);<br /> 55 }<br /> 56 j++;<br /> 57 }<br /> 58 swap(&a[e],&a[i+1]);<br /> 59 return i+1;<br /> 60 }<br /> 61 void swap(int *a,int *b)<br /> 62 {<br /> 63 int tmp = *a;<br /> 64 *a = *b;<br /> 65 *b = tmp;<br /> 66 }<br />

关于paration的另一种写法如下：

但是这种写法非常容易出错，必须遵循：

（1）如果取中枢元素m=a[e](即结尾元素)，必须保证先做low的自增操作，然后是high的自减操作。

（2）如果取中枢元素m=a[s](即起始元素)，必须保证先做high的自减操作，然后是high的自增操作。（代码中所示）

否则将会出现错误。测试案例如3,3,3,1,5,2,4等。

39 int paration(int *a,int s,int e)<br /> 40 {<br /> 41 int m = a[e];<br /> 42 int l = s;<br /> 43 int h = e;<br /> 44 while(l<h)<br /> 45 {<br /> 46 while(l<h && a[l]<=m)<br /> 47 l++;<br /> 48 swap(&a[l],&a[h]);<br /> 49 while(l<h && a[h]>=m)<br /> 50 h--;<br /> 51 swap(&a[h],&a[l]);<br /> 52<br /> 53 }<br /> 54 return l;<br /> 55 }