[[121946]]

前言

之前，曾在本BLOG內(nèi)寫過一篇文章，快速排序算法普及教程，不少網(wǎng)友反映此文好懂。然，后來有網(wǎng)友algorithm__，指出，“快速排序算法怎么一步一步想到的列?就如一個P與NP問題。知道了解，證明不難。可不知道解之前，要一點一點、一步一步推導出來，好難阿?”

其實，這個問題，我也想過很多次了。之前，也曾在博客里多次提到過。那么，到底為什么，有不少人看了我寫的快速排序算法，過了一段時間后，又不清楚快排是怎么一回事了列?

“很大一部分原因，就是只知其表，不知其里，只知其用，不知其本質(zhì)。很多東西，都是可以從本質(zhì)看本質(zhì)的。而大部分人沒有做到這一點。從而看了又忘，忘了再看，如此，在對知識的一次一次重復記憶中，始終未能透析本質(zhì)，從而，形成不好的循環(huán)。

所以，歸根究底，學一個東西，不但要運用自如，還要通曉其原理，來龍去脈與本質(zhì)。正如侯捷先生所言，只知一個東西的用法，卻不知其原理，實在不算高明。你提出的問題，非常好。我會再寫一篇文章，徹底闡述快速排序算法是如何設(shè)計的，以及怎么一步一步來的。”

ok，那么現(xiàn)在，我就來徹底分析下此快速排序算法，希望能讓讀者真正理解此算法，通曉其來龍去脈，明白其內(nèi)部原理。本文著重分析快速排序算法的過程來源及其時間復雜度。

一、快速排序最初的版本

快速排序的算法思想(此時，還不叫做快速排序)最初是由，一個名叫C.A.R.Hoare提出的，他給出的算法思想描述的具體版本，如下：

HOARE-PARTITION(A, p, r)

x ← A[p] 
i ← p - 1 
j ← r + 1 
while TRUE 
    do repeat j ← j - 1 
         until A[j] ≤ x 
       repeat i ← i + 1 
         until A[i] ≥ x 
       if i < j 
          then exchange A[i] ↔ A[j] 
          else return j 

后來，此版本又有不少的類似變種。下面，會具體分析。

二、Hoare版本的具體分析

Hoare在算法導論第7章***的思考題7-1有所闡述。

在上面，我們已經(jīng)知道，Hoare的快速排序版本可以通過前后倆個指針，分別指向首尾，分別比較而進行排序。

下面，分析一下此版本：

I、 倆個指針，i指向序列的首部，j指著尾部，即i=1，j=n，取數(shù)組中***個元素ki為主元，即key<-ki(賦值)。

II、賦值操作（注，以下“->”，表示的是賦值）：

j(找小)，從右至左，不斷--，直到遇到***個比key小的元素kj，ki<-kj。

i(找大)，從左至右，不斷++，直到遇到***個比key大的元素ki，kj<-ki。

III、按上述方式不斷進行，直到i，j碰頭，ki=key，***趟排序完成接下來重復II步驟，遞歸進行。

當過程HOARE-PARTITION結(jié)束后，A[p..j](此處在算法導論中文版第二版中出現(xiàn)了印刷錯誤，被印成了A[p..r])中的每個元素都小于或等于A[j+1..r]每一個元素。HOARE-PARTITION與下文將要介紹的標準PARTITION劃分方法不同，HOARE-PARTITION總是將主元值放入兩個劃分A[p..j]和A[j+1..r]中的某一個之中。因為p<<j<<r，故這種劃分總是會結(jié)束的。

接下來，咱們來看下上述HOARE-PARTITION劃分方法在數(shù)組A=[13，19,9,5,12,8,7,4,11,2,6,21]上的運行過程，如下：

i（找大） （找?。﹋

13 19 9 5 12 8 7 4 11 2 6 21

i j

13 19 9 5 12 8 7 4 11 2 6 21

i j

6 19 9 5 12 8 7 4 11 2 13 21

j i

6 2 9 5 12 8 7 4 11 19 13 21

i j

6 2 9 5 12 8 7 4 11 19 13 21

i j

4 2 9 5 12 8 7 6 11 19 13 21

ij

4 2 5 9 12 8 7 6 11 19 13 21

    .....

2 4 5 6 7 8 9 11 12 13 19 21

三、Hoare變種版本

I、取倆個指針i，j，開始時，i=2，j=n，且我們確定，最終完成排序時，左邊子序列的數(shù)<=右邊子序列。

II、矯正位置，不斷交換

i-->(i從左至右，右移，找比***個元素要大的)

通過比較ki與k1，如果Ri在分劃之后最終要成為左邊子序列的一部分，

則i++，且不斷i++，直到遇到一個該屬于右邊子序列Ri(較大)為止。

<--j(j從右至左，左移，找比***個元素要小的)

類似的，j--，直到遇到一個該屬于左邊子序列的較小元素Rj(較小)為止，

如此，當i<j時，交換Ri與Rj，即擺正位置麻，把較小的放左邊，較大的放右邊。

III、然后以同樣的方式處理劃分的記錄，直到i與j碰頭為止。這樣，不斷的通過交換Ri，Rj擺正位置，最終完成整個序列的排序。

舉個例子，如下(2為主元)：

         i->                      <-j(找小)

    2   8   7   1   3   5   6   4

j所指元素4，大于2，所以，j--，

         i                   <--j

    2   8   7   1   3   5   6   4

此過程中，若j 沒有遇到比2小的元素，則j 不斷--，直到j(luò) 指向了1，

         i         j

    2   8   7   1   3   5   6   4

此刻，8與1互換，

          i        j

    2   1   7   8   3   5   6   4

此刻，i 所指元素1，小于2，所以i不動，，j 繼續(xù)--，始終沒有遇到再比2小的元素，最終停至7。

          i   j

    2   1   7   8   3   5   6   4

***，i 所指元素1，與數(shù)列中***個元素k1，即2交換，

          i   

  [1]   2   [7   8   3   5   6   4]

這樣，2就把整個序列，排成了2個部分，接下來，再對剩余待排序的數(shù)遞歸進行第二趟、第三趟排序....。

由以上的過程，還是可以大致看出此算法的拙陋之處的。如一，在上述***步過程中，j沒有找到比2小的元素時，需不斷的前移，j--。二，當i所指元素交換 后，無法確保此刻i所指的元素就一定小于2，即i指針，還有可能繼續(xù)停留在原處，不能移動。如此停留，勢必應該會耗費不少時間。

后來，進一步，sedgewick因其排序速率較快，便稱之為"快速排序"，快速排序也因此而誕生了。并最終一舉成名，成為了二十世紀最偉大的10大算法之一。

OK，接下來，咱們來看Hoare的變種版本算法。如下，對序列3   8   7   1   2   5   6   4，進行排序：

1、j--，直到遇到了序列中***個比key值3小的元素2，把2賦給ki，j 此刻指向了空元素。

           i                                 j

          3   8   7   1   2   5   6   4

          i                   j

   =>  2   8   7   1       5   6   4

2、i++，指向8，把8重置給j 所指元素空白處，i 所指元素又為空：

               i              j

          2   8   7   1       5   6   4

               i             j

=>   2       7   1   8   5   6   4

3、j繼續(xù)--，遇到了1，還是比3(事先保存的key值)小，1賦給i所指空白處：

                i       j

          2       7   1   8   5   6   4

   =>   2   1   7       8   5   6   4

4、同理，i 又繼續(xù)++，遇到了7，比key大，7賦給j所指空白處，此后，i，j碰頭。***趟結(jié)束：

                    i    j

          2   1   7       8   5   6   4

                    i    j

   =>   2   1       7   8   5   6   4

5、***，事先保存的key，即3賦給ki，即i所指空白處，得：

          [2  1]  3  [7   8   5   6   4]

所以，整趟下來，便是這樣：

          3   8   7   1   2   5   6   4

          2   8   7   1   3   5   6   4

          2   3   7   1   8   5   6   4

          2   1   7   3   8   5   6   4

          2   1   3   7   8   5   6   4

          2   1   3   7   8   5   6   4

后續(xù)補充：

如果待排序的序列是逆序數(shù)列列?ok，為了說明的在清楚點，再舉個例子，對序列 9 8 7 6 5 4 3 2 1排序：

    9 8 7 6 5 4 3 2 1 //9為主元

    1 8 7 6 5 4 3 2   //j從右向左找小，找到1，賦給***個

    1 8 7 6 5 4 3 2   //i從左向右找大，沒有找到，直到與j碰頭

    1 8 7 6 5 4 3 2 9 //***，填上9.   

如上，當數(shù)組已經(jīng)是逆序排列好的話，我們很容易就能知道，此時數(shù)組排序需要O(N^2)的時間復雜度。稍后下文，會具體分析快速排序的時間復雜度。

***，寫程序?qū)崿F(xiàn)此算法，如下，相信，不用我過多解釋了：

 

int partition(int data[],int lo,int hi)  //引自whatever。 
 
{ 
 
    int key=data[lo]; 
 
    int l=lo; 
 
    int h=hi; 
 
    while(l<h) 
 
   { 
 
       while(key<=data[h] && l<h) h--;   //高位找小，找到了，就把它弄到前面去 
 
          data[l]=data[h]; 
 
       while(data[l]<=key && l<h) l++;    //低位找大，找到了，就把它弄到后面去 
 
         data[h]=data[l]; 
 
   }                                                   //如此，小的在前，大的在后，一分為二 
 
    data[l]=key; 
 
    return l; 
 
} 

后續(xù)補充：舉個例子，如下（只說明了***趟排序）：

        3   8   7   1   2   5   6   4

        2   8   7   1       5   6   4

        2       7   1   8   5   6   4

        2   1   7       8   5   6   4

        2   1       7   8   5   6   4

        2   1   3   7   8   5   6   4   //***補上，關(guān)鍵字3

看到這，不知各位讀者，有沒有想到我上一篇文章里頭的那快速排序的第二個版本?對，上述程序，即那篇文章里頭的第二個版本。我把程序揪出來，你一看，就明白了：

 

void quicksort(table *tab,int left,int right) 
{ 
  int i,j; 
  if(left<right) 
  { 
    i=left;j=right; 
    tab->r[0]=tab->r[i]; //準備以本次最左邊的元素值為標準進行劃分，先保存其值 
    do 
    { 
      while(tab->r[j].key>tab->r[0].key&&i<j) 
        j--;        //從右向左找第1個小于標準值的位置j 
      if(i<j)                               //找到了，位置為j 
      { 
        tab->r[i].key=tab->r[j].key;i++; 
 
      }           //將第j個元素置于左端并重置i 
 
      while(tab->r[i].key<tab->r[0].key&&i<j) 
 
        i++;      //從左向右找第1個大于標準值的位置i 
 
      if(i<j)                       //找到了，位置為i 
      { 
        tab->r[j].key=tab->r[i].key;j--; 
      }           //將第i個元素置于右端并重置j 
 
    }while(i!=j); 
    tab->r[i]=tab->r[0];         //將標準值放入它的最終位置,本次劃分結(jié)束 
    quicksort(tab,left,i-1);     //對標準值左半部遞歸調(diào)用本函數(shù) 
    quicksort(tab,i+1,right);    //對標準值右半部遞歸調(diào)用本函數(shù) 
  } 
} 

我想，至此，已經(jīng)講的足夠明白了。如果，你還不懂的話，好吧，伸出你的手指，數(shù)數(shù)吧....ok，再問讀者一個問題：像這種i從左至右找大，找到***個比 key大(數(shù)組中***個元素置為key)，便重置kj，j從右向左找小，找到***個比key小的元素，則重置ki，當然此過程中，i，j都在不斷的變化， 通過++，或--，指向著不同的元素。

你是否聯(lián)想到了，現(xiàn)實生活中，有什么樣的情形，與此快速排序算法思想相似?ok，等你想到了，再告訴我，亦不遲。:D。

四、快速排序的優(yōu)化版本

再到后來，N.Lomuto又提出了一種新的版本，此版本即為快速排序算法中闡述的***個版本，即優(yōu)化了PARTITION程序，它現(xiàn)在寫在了 算法導論 一書上，

快速排序算法的關(guān)鍵是PARTITION過程，它對A[p..r]進行就地重排：

PARTITION(A, p, r)

 

x ← A[r]         //以***一個元素，A[r]為主元 
i ← p - 1 
for j ← p to r - 1    //注，j從p指向的是r-1，不是r。 
 
     do if A[j] ≤ x 
           then i ← i + 1 
                exchange A[i] <-> A[j] 
exchange A[i + 1] <-> A[r] 
return i + 1 

然后，對整個數(shù)組進行遞歸排序：

 

QUICKSORT(A, p, r) 
 if p < r 
    then q ← PARTITION(A, p, r)   //關(guān)鍵 
         QUICKSORT(A, p, q - 1) 
         QUICKSORT(A, q + 1, r) 

舉最開頭的那個例子：2   8   7   1   3   5   6   4，不過與上不同的是：它不再以***個元素為主元，而是以***一個元素4為主元，且i，j倆指針都從頭出發(fā)，j 一前，i 一后。i 指元素的前一個位置，j 指著待排序數(shù)列中的***個元素。

一、

i p/j-->

  2   8   7   1   3   5   6   4(主元)

j 指的2<=4，于是i++，i 也指到2，2和2互換，原數(shù)組不變。

j 后移，直到指向1..

二、

              j（指向1）<=4，于是i++，i指向了8，

       i         j

  2   8   7   1   3   5   6   4

所以8與1交換，數(shù)組變成了：

        i        j

  2   1   7   8   3   5   6   4

三、j 后移，指向了3,3<=4，于是i++

i 這時指向了7，

             i        j

  2   1   7   8   3   5   6   4

于是7與3交換，數(shù)組變成了：

             i        j

  2   1   3   8   7   5   6   4

四、j 繼續(xù)后移，發(fā)現(xiàn)沒有再比4小的數(shù)，所以，執(zhí)行到了***一步，

即上述PARTITION(A, p, r)代碼部分的 第7行。

因此，i后移一個單位，指向了8

                 i              j

  2   1   3   8   7   5   6   4

A[i + 1] <-> A[r]，即8與4交換，所以，數(shù)組最終變成了如下形式，

  2   1   3   4   7   5   6   8

ok，快速排序***趟完成。接下來的過程，略。不過，有個問題，你能發(fā)現(xiàn)此版本與上述版本的優(yōu)化之處么?

五、快速排序的深入分析

咱們，再具體分析下上述的優(yōu)化版本，

 

PARTITION(A, p, r) 
  x ← A[r] 
  i ← p - 1 
  for j ← p to r - 1 
       do if A[j] ≤ x 
             then i ← i + 1 
                  exchange A[i] <-> A[j] 
  exchange A[i + 1] <-> A[r] 
  return i + 1 

咱們以下數(shù)組進行排序，每一步的變化過程是：

i p/j

  2   8   7   1   3   5   6   4(主元)

       i         j

  2   1   7   8   3   5   6   4

            i         j

  2   1   3   8   7   5   6   4

                 i

  2   1   3   4   7   5   6   8

由上述過程，可看出，j掃描了整個數(shù)組一遍，只要一旦遇到比4小的元素，i 就++，然后，kj、ki交換。那么，為什么當j找到比4小的元素后，i 要++列? 你想麻，如果i始終停在原地不動，與kj 每次交換的ki不就是同一個元素了么?如此，還談什么排序?。

所以，j在前面開路，i跟在j后，j只要遇到比4小的元素，i 就向前前進一步，然后把j找到的比4小的元素，賦給i，然后，j才再前進。

打個比喻就是，你可以這么認為，i所經(jīng)過的每一步，都必須是比4小的元素，否則，i就不能繼續(xù)前行。好比j 是先行者，為i 開路搭橋，把小的元素作為跳板放到i 跟前，為其鋪路前行啊。

于此，j掃描到***，也已經(jīng)完全排查出了比4小的元素，只有***一個主元4，則交給i處理，因為***一步，exchange A[i + 1] <-> A[r]。這樣，不但完全確保了只要是比4小的元素，都被交換到了數(shù)組的前面，且j之前未處理的比較大的元素則被交換到了后面，而且還是O（N）的時間復雜度，你不得不佩服此算法設(shè)計的巧妙。

這樣，我就有一個問題了，上述的PARTITION(A, p, r)版本，可不可以改成這樣咧?

望讀者思考：

 

PARTITION(A, p, r)   //請讀者思考版本。 
  x ← A[r] 
  i ← p - 1 
  for j ← p to r      //讓j 從p指向了***一個元素r 
       do if A[j] ≤ x 
             then i ← i + 1 
                  exchange A[i] <-> A[j] 
  exchange A[i + 1] <-> A[r]   //去掉此***的步驟 
  return i      //返回 i，不再返回 i+1. 

六、Hoare變種版本與優(yōu)化后版本的比較

現(xiàn)在，咱們來討論一個問題，快速排序中，其中對于序列的劃分，我們可以看到，已經(jīng)有以上倆個版本，那么這倆個版本孰優(yōu)孰劣列?ok，不急，咱們來比較下：

為了看著方便，再貼一下各自的算法，

Hoare變種版本：

HOARE-PARTITION(A, p, r)

 

x ← A[p]       //以***個元素為主元 
i ← p - 1 
j ← r + 1 
while TRUE 
    do repeat j ← j - 1 
         until A[j] ≤ x 
       repeat i ← i + 1 
         until A[i] ≥ x 
       if i < j 
          then exchange A[i] ↔ A[j] 
          else return j 

優(yōu)化后的算法導論上的版本：

 

PARTITION(A, p, r) 
  x ← A[r]         //以***一個元素，A[r]為主元 
  i ← p - 1 
  for j ← p to r - 1    
       do if A[j] ≤ x 
             then i ← i + 1 
                  exchange A[i] <-> A[j] 
  exchange A[i + 1] <-> A[r] 
  return i + 1 

咱們，先舉上述說明Hoare版本的這個例子，對序列3   8   7   1   2   5   6   4，進行排序：

Hoare變種版本（以3為主元，紅體為主元）：

3   8   7   1   2   5   6   4  

2   8   7   1       5   6   4   //交換1次，比較4次

2       7   1   8   5   6   4   //交換1次，比較1次

2   1   7       8   5   6   4   //交換1次，比較1次

2   1       7   8   5   6   4   //交換1次，比較0次

2   1   3   7   8   5   6   4   //總計交換4次，比較6次。

                                //移動了元素3、8、7、1、2.移動范圍為：2+3+1+2+4=12.

優(yōu)化版本（以4為主元）：

3   8   7   1   2   5   6   4   //3與3交換，不用移動元素，比較1次

3   1   7   8   2   5   6   4   //交換1次，比較3次

3   1   2   8   7   5   6   4   //交換1次，比較1次

3   1   2   4   7   5   6   8   //交換1次，比較2次。

                                //即完成，總計交換4次，比較7次。

                                //移動了元素8、7、1、2、4.移動范圍為：6+2+2+2+4=16.

 再舉一個例子：對序列2   8   7   1   3   5   6   4排序：

Hoare變種版本：

2   8   7   1   3   5   6   4 

1   8   7       3   5   6   4  //交換1次，比較5次

1       7   8   3   5   6   4  //交換1次，比較1次

1   2   7   8   3   5   6   4  //交換0次，比較1次。2填上，完成，總計交換2次，比較7次。

優(yōu)化版本：

2   8   7   1   3   5   6   4 //2與2交換，比較1次

2   1   7   8   3   5   6   4 //交換1次，比較3次

2   1   3   8   7   5   6   4 //交換1次，比較1次

2   1   3   4   7   5   6   8 //交換1次，比較2次。完成，總計交換4次，比較7次。

各位，已經(jīng)看出來了，這倆個例子說明不了任何問題。到底哪個版本效率更高，還有待進一步驗證或者數(shù)學證明。ok，等我日后發(fā)現(xiàn)更有利的證據(jù)再來論證下。 

七、快速排序算法的時間復雜度

ok，我想你已經(jīng)完全理解了此快速排序，那么，我想你應該也能很快的判斷出：快速排序算法的平均時間復雜度，即為O(nlgn)。為什么列?因為你 看，j，i掃描一遍數(shù)組，花費用時多少?對了，掃描一遍，當然是O(n)了，那樣，掃描多少遍列，lgn到n遍，最快lgn，最慢n遍。且可證得，快速排序的平均時間復雜度即為O(n*lgn)。

PARTITION可能做的最平衡的劃分中，得到的每個子問題都不能大于n/2.

因為其中一個子問題的大小為|_n/2_|。另一個子問題的大小為|-n/2-|-1.

在這種情況下，快速排序的速度要快得多。為：

T(n)<=2T（n/2）+O（n）.可以證得，T（n）=O（nlgn）。

以下給出一個遞歸樹的簡單證明：

在分治算法中的三個步驟中， 我們假設(shè)分解和合并過程所用的時間分別為D(n), C(n), 設(shè)T(n)為處理一個規(guī)模為n的序列所消耗的時間為子序列個數(shù)，每一個子序列是原序列的1/b，α為把每個問題分解成α個子問題, 則所消耗的時間為：

               O（1）      如果n<=c

     T(n) =

              αT(n/b) + D(n) + C(n)

在快速排序中,α 是為2的, b也為2, 則分解(就是取參照點,可以認為是1), 合并(把數(shù)組合并,為n), 因此D(n) + C(n) 是一個線性時間O(n).這樣時間就變成了：

T(n) = 2T(n/2) + O(n).

如上圖所示，在每個層的時間復雜度為: O(n)，一共有Lgn層,每一層上都是cn, 所以共消耗時間為cn*lgn; 則總時間:

cn*lg2n+cn = cn(1+lgn)  即O(nlgn)。

關(guān)于T(n)<=2T（n/2）+O（n）=>T（n）=O（nlgn）的嚴格數(shù)學證明，可參考算法導論 第四章 遞歸式。

而后，我想問讀者一個問題，由此快速排序算法的時間復雜度，你想到了什么，是否想到了歸并排序的時間復雜度，是否想到了二分查找，是否想到了一課n個結(jié)點的紅黑樹的高度lgn，是否想到了......

八、由快速排序所想到的

上述提到的東西，很早以前就想過了。此刻，我倒是想到了前幾天看到的一個荷蘭國旗問題。當時，和algorithm__、gnuhpc簡單討論過這個問題。現(xiàn)在，我也來具體解決下此問題：

問題描述：

我們將亂序的紅白藍三色小球排列成有序的紅白藍三色的同顏色在一起的小球組。這個問題之所以叫荷蘭國旗，是因為我們可以將紅白藍三色小球想象成條狀物，有序排列后正好組成荷蘭國旗。如下圖所示：

[[121948]]

這個問題，類似快排中partition過程。不過，要用三個指針，一前begin，一中current，一后end，倆倆交換。

1、current遍歷，整個數(shù)組序列，current指1不動，

2、current指0，與begin交換，而后current++，begin++，

3、current指2，與end交換，而后，current不動，end--。

為什么，第三步，current指2，與end交換之后，current不動了列，對的，正如algorithm__所說：current之所以與 begin交換后，current++、begin++，是因為此無后顧之憂。而current與end交換后，current不動，end--，是因有 后顧之憂。

為什么啊，因為你想想啊，你最終的目的無非就是為了讓0、1、2有序排列，試想，如果第三步，current與end交換之前，萬一end之前指的是0， 而current交換之后，current此刻指的是0了，此時，current能動么？不能動啊，指的是0，還得與begin交換列。

ok，說這么多，你可能不甚明了，直接引用下gnuhpc的圖，就一目了然了：   

   

本程序主體的代碼是：

//引用自gnuhpc 
while( current<=end )      
{           
  if( array[current] ==0 )           
   {               
      swap(array[current],array[begin]);                
      current++;                
      begin++;          
   }           
   else if( array[current] == 1 )          
   {               
      current++;          
   } 
else //When array[current] =2 
   {             
      swap(array[current],array[end]);              
      end--;          
   }    
} 

看似，此問題與本文關(guān)系不大，但是，一來因其余本文中快速排序partition的過程類似，二來因為此問題引發(fā)了一段小小的思考，并最終成就了本文。差點忘了，還沒回答本文開頭提出的問題。所以，快速排序算法是如何想到的，如何一步一步發(fā)明的列?答案很簡單：多觀察，多思考。

ok，測試一下，看看你平時有沒有多觀察、多思考的習慣：我不知道是否有人真正思考過冒泡排序，如果思考過了，你是否想過，怎樣改進冒泡排序列?ok，其它的，我就不多說了，只貼以下這張圖：

本文完。

作者:July