[[121946]]

前言

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

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

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

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

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

一、快速排序最初的版本

快速排序的算法思想(此時(shí)，還不叫做快速排序)最初是由，一個(gè)名叫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 

后來(lái)，此版本又有不少的類似變種。下面，會(huì)具體分析。

二、Hoare版本的具體分析

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

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

下面，分析一下此版本：

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

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

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

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

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

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

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

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、取倆個(gè)指針i，j，開(kāi)始時(shí)，i=2，j=n，且我們確定，最終完成排序時(shí)，左邊子序列的數(shù)<=右邊子序列。

II、矯正位置，不斷交換

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

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

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

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

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

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

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

舉個(gè)例子，如下(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

此過(guò)程中，若j 沒(méi)有遇到比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不動(dòng)，，j 繼續(xù)--，始終沒(méi)有遇到再比2小的元素，最終停至7。

          i   j

    2   1   7   8   3   5   6   4

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

          i   

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

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

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

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

OK，接下來(lái)，咱們來(lái)看Hoare的變種版本算法。如下，對(duì)序列3   8   7   1   2   5   6   4，進(jìn)行排序：

1、j--，直到遇到了序列中***個(gè)比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]

所以，整趟下來(lái)，便是這樣：

          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ù)補(bǔ)充：

如果待排序的序列是逆序數(shù)列列?ok，為了說(shuō)明的在清楚點(diǎn)，再舉個(gè)例子，對(duì)序列 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，賦給***個(gè)

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

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

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

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

 

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ù)補(bǔ)充：舉個(gè)例子，如下（只說(shuō)明了***趟排序）：

        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   //***補(bǔ)上，關(guān)鍵字3

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

 

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

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

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

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

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

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

PARTITION(A, p, r)

 

x ← A[r]         //以***一個(gè)元素，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 

然后，對(duì)整個(gè)數(shù)組進(jìn)行遞歸排序：

 

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) 

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

一、

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 這時(shí)指向了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)沒(méi)有再比4小的數(shù)，所以，執(zhí)行到了***一步，

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

因此，i后移一個(gè)單位，指向了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，快速排序***趟完成。接下來(lái)的過(guò)程，略。不過(guò)，有個(gè)問(wèn)題，你能發(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ù)組進(jìn)行排序，每一步的變化過(guò)程是：

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

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

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

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

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

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

望讀者思考：

 

PARTITION(A, p, r)   //請(qǐng)讀者思考版本。 
  x ← A[r] 
  i ← p - 1 
  for j ← p to r      //讓j 從p指向了***一個(gè)元素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)在，咱們來(lái)討論一個(gè)問(wèn)題，快速排序中，其中對(duì)于序列的劃分，我們可以看到，已經(jīng)有以上倆個(gè)版本，那么這倆個(gè)版本孰優(yōu)孰劣列?ok，不急，咱們來(lái)比較下：

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

Hoare變種版本：

HOARE-PARTITION(A, p, r)

 

x ← A[p]       //以***個(gè)元素為主元 
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)化后的算法導(dǎo)論上的版本：

 

PARTITION(A, p, r) 
  x ← A[r]         //以***一個(gè)元素，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 

咱們，先舉上述說(shuō)明Hoare版本的這個(gè)例子，對(duì)序列3   8   7   1   2   5   6   4，進(jìn)行排序：

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   //總計(jì)交換4次，比較6次。

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

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

3   8   7   1   2   5   6   4   //3與3交換，不用移動(dòng)元素，比較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次。

                                //即完成，總計(jì)交換4次，比較7次。

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

 再舉一個(gè)例子：對(duì)序列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填上，完成，總計(jì)交換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次。完成，總計(jì)交換4次，比較7次。

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

七、快速排序算法的時(shí)間復(fù)雜度

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

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

因?yàn)槠渲幸粋€(gè)子問(wèn)題的大小為|_n/2_|。另一個(gè)子問(wèn)題的大小為|-n/2-|-1.

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

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

以下給出一個(gè)遞歸樹(shù)的簡(jiǎn)單證明：

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

               O（1）      如果n<=c

     T(n) =

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

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

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

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

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

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

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

八、由快速排序所想到的

上述提到的東西，很早以前就想過(guò)了。此刻，我倒是想到了前幾天看到的一個(gè)荷蘭國(guó)旗問(wèn)題。當(dāng)時(shí)，和algorithm__、gnuhpc簡(jiǎn)單討論過(guò)這個(gè)問(wèn)題?，F(xiàn)在，我也來(lái)具體解決下此問(wèn)題：

問(wèn)題描述：

我們將亂序的紅白藍(lán)三色小球排列成有序的紅白藍(lán)三色的同顏色在一起的小球組。這個(gè)問(wèn)題之所以叫荷蘭國(guó)旗，是因?yàn)槲覀兛梢詫⒓t白藍(lán)三色小球想象成條狀物，有序排列后正好組成荷蘭國(guó)旗。如下圖所示：

[[121948]]

這個(gè)問(wèn)題，類似快排中partition過(guò)程。不過(guò)，要用三個(gè)指針，一前begin，一中current，一后end，倆倆交換。

1、current遍歷，整個(gè)數(shù)組序列，current指1不動(dòng)，

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

3、current指2，與end交換，而后，current不動(dòng)，end--。

為什么，第三步，current指2，與end交換之后，current不動(dòng)了列，對(duì)的，正如algorithm__所說(shuō)：current之所以與 begin交換后，current++、begin++，是因?yàn)榇藷o(wú)后顧之憂。而current與end交換后，current不動(dòng)，end--，是因有 后顧之憂。

為什么啊，因?yàn)槟阆胂氚?，你最終的目的無(wú)非就是為了讓0、1、2有序排列，試想，如果第三步，current與end交換之前，萬(wàn)一end之前指的是0， 而current交換之后，current此刻指的是0了，此時(shí)，current能動(dòng)么？不能動(dòng)啊，指的是0，還得與begin交換列。

ok，說(shuō)這么多，你可能不甚明了，直接引用下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--;          
   }    
} 

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

ok，測(cè)試一下，看看你平時(shí)有沒(méi)有多觀察、多思考的習(xí)慣：我不知道是否有人真正思考過(guò)冒泡排序，如果思考過(guò)了，你是否想過(guò)，怎樣改進(jìn)冒泡排序列?ok，其它的，我就不多說(shuō)了，只貼以下這張圖：

本文完。

作者:July