關於快速排序中元素調整方法的分析
快速排序的相關資料網上有很多，基本的思路也比較簡單：找一個基準值，將元素分成兩部分，然後遞歸繼續。
其中一直困擾我的一個點就是將元素分成兩部分的問題，大部分文章都只講方法，或者演示方法，但說實話我有點懵，因為我並沒有搞清楚為什麼這樣那樣做就能將元素調整為兩部分，只是勉強記住了方法。
最近又碰到了這個問題，在網上查了很多資料，感覺終於搞清楚了，總結如下：
方法一：單向調整，最簡單易懂
1 /*單向調整，將元素按基準值分成三部分*/ 2 int pa(int a[],int left,int right) 3 { 4 /*為什麼要按基準值分成三部分？ 5 如何分成兩部分的話，某些情況會出現死循環 6 例如將 2 3 4 5 3 分成兩部分，得到的將是 |2 3 4 5 3 ，等於沒分 7 下次遞歸會導致 left與mid值相等，進入死循環*/ 8 9 int key=a[left];//選取基準值 10 int t,i,j; 11 /*核心思路：讓i左邊的元素必須小於key，或者說讓小於key的元素都在i左邊 12 此循環將元素分成兩部分： 13 a[left+1]~a[i-1]小於key，a[i]~a[right]大於等於key*/ 14 for(i=j=left+1;j<=right;j++) 15 { 16 if(a[j]<key) 17 { 18 t=a[i];a[i]=a[j];a[j]=t; 19 i++; 20 } 21 } 22 /*a[left]等於key，a[i-1]肯定小於key，交換後可以保證： 23 i-1左邊的元素小於key，i-1指向的元素等於key，i-1右邊的元素大於等於key*/ 24 t=a[i-1];a[i-1]=a[left];a[left]=t; 25 return i-1; 26 }
方法二：雙向調整，其實只是對方法一的優化
/*雙向調整1：參考單向調整的方法，將元素分成三部分*/ int pa(int a[],int left,int right) { int i,j,t,key; key=a[left]; i=left+1,j=right; while(i<=j) { //核心思路：讓i左邊的元素必須小於key，或者說讓小於key的元素都在i左邊 while(a[i]<key&&i<=j)i++;//循環後a[i]>=key while(a[j]>=key&&i<=j)j--;//循環後a[j]<key //為什麼要考慮i==j的情況？所有元素都小於key的情況下會出錯 if(i<=j) { t=a[i];a[i]=a[j];a[j]=t; i++;j--; } } t=a[left];a[left]=a[i-1];a[i-1]=t; return i-1; }
//sort()函數同上一個方法
方法三：雙向調整，最常用的一種方法。
/*雙向調整2：將元素分成 [i,right]、(j,i)、[left,j]三部分*/ void sort(int a[],int left,int right) { int i,j,t,key; key=a[left]; i=left,j=right; while(i<=j)//為什麼要取等於？為了將元素分成三部分 { //讓i左邊元素小於key，循環後a[i]大於等於key while(a[i]<key)i++; //讓j右邊元素大於key，循環後a[j]小於等於key while(a[j]>key)j--; if(i<=j) { /*交換a[i] a[j]的值，i,j繼續前進 因為交換，所以 a[i]左邊的元素實際上小於等於key a[j]右邊的元素實際上大於等於key*/ t=a[i];a[i]=a[j];a[j]=t; i++,j--; } } /*循環結束後j<i [i,right]的元素大於等於key， [left,j]的元素小於等於key (j,i)的元素等於key */ if(i<right)sort(a,i,right); if(left<j)sort(a,left,j); }
