快排有多快

說到快我只推崇葵花寶典,那叫一個快啊～～～

皮一下哈哈,言歸正傳。快速排序算法如其名一樣,快!來看看快排和其他幾大排序算法的并行運行對比視頻(中間那個就是快排),你就知道它到底有多快了,請全屏橫屏播放更清晰:

啥是快排? 分治思想

從待排元素集中選取一個元素作為擺動基準pivot,pivot這詞比較形象,如上圖像一個軸一樣在擺動。記為P將元素重新排列為3個子塊:左子塊S1:由P的元素組成中間塊M:僅有P一個元素右子塊S2:由≥P的元素組成對左子塊S1和右子塊S2遞歸地重復(fù)上述過程,Return {quicksort(S 1 ), P, quicksort(S 2 )}．

代碼實現(xiàn)

代碼如下:

typedef int T_ELEMENT;
int partition(T_ELEMENT A[ ], int left, int right);
sort A[left．．right]
void quicksort(T_ELEMENT A[ ], int left, int right)
{  
 int q;
 if( right <= left )
     return;
 if ( right > left )
 {  
    q = partition(A, left, right);
     partition分塊后
    //-> A[left．．q-1] ≤ A[q] ≤ A[q+1．．right]
    quicksort(A, left, q-1);    
    quicksort(A, q+1, right);
  }
}
int partition(T_ELEMENT A[], int left, int right);
{
   T_ELEMENT P = A[left];
   i = left;
   j = right + 1;
   無限循環(huán),使用break退出
   for(;;)
   {
       while (A[++i] < P) if (i >= right) break;
        此時 A[i] ≥ P
       while (A[--j] > P) if (j <= left) break;
        此時 A[j] ≤ P
       if (i >= j ) break; 退出for循環(huán)
       else swap(A[i], A[j]);
   }
   if (j == left) return j ;
   swap(A[left], A[j]);
   return j;
}

舉栗子分析:

分成三塊了,再遞歸子塊迭代,直到right<=left． 這里放一個全過程慢鏡頭動圖,幫助理解:

算法分析 

這種快速排序的優(yōu)點是我們可以“就地”排序,即無需依賴于輸入大小的臨時緩沖區(qū)。沒有緩沖區(qū)內(nèi)存開銷,僅有棧開銷。(注還有一種非遞歸的棧實現(xiàn)版本,本文就先不聊了)partition步驟:時間復(fù)雜度為θ(n)。快速排序涉及分區(qū)和2個遞歸調(diào)用。故:

T(n) = θ(n) + T(i) + T(n-i-1) = cn+ T(i) + T(n-i-1)

其中,i是分區(qū)后第一個子塊的大小,將T(0)=T(1)= 1作為初始條件。

具體運行時間對不同特性的待排數(shù)據(jù),其結(jié)果差異比較大,來看一下最好、最壞以及平均情況分析。最差情況當待排數(shù)據(jù)序列為正序或者逆序時,pivot將是在大小為n的待排塊時中的最小(或最大)元素時。則階段1迭代中生成一個空子塊、pivot,及一個大小(n-1)的子塊,則時間復(fù)雜度為θ(n)遞歸方程:

如果這種情況在每個分區(qū)中都重復(fù)發(fā)生,那么每個遞歸調(diào)用處理一個比前一個列表小1的列表。因此需要在達到大小為1的列表之前進行n - 1次嵌套調(diào)用。這意味著調(diào)用樹是n - 1個嵌套調(diào)用的線性鏈。第i次調(diào)用需要做O(n-i)復(fù)雜度來進行分區(qū),則

最好情況

如每次分區(qū)時樞軸(pivot)都能取到中間值,即每次分區(qū)后,將產(chǎn)生兩個大小大致相等的子塊,并且樞軸(pivot)元素處于中間值位置,需要做n次比較運算。

遞歸方程:

如前所說,如每次執(zhí)行分區(qū)時,都能將列表分成兩個幾乎相等的兩個子塊。這意味著每次遞歸調(diào)用都要處理一個只有一半大小的列表。因此,在到達大小為1的列表之前,我們只能進行嵌套調(diào)用。這意味著調(diào)用樹的深度為,但是在調(diào)用樹的同一級別上沒有兩個調(diào)用處理原始列表的相同部分;因此,每個級別的調(diào)用總共只需要O(n)個時間(每個調(diào)用都有一些固定的開銷,但是由于每個級別上只有O(n)個調(diào)用,所以這被包含在O(n)因子中)。結(jié)果是,該算法只使用c(n log n)的時間。故時間復(fù)雜度為O(n log n)。

平均情況

要對n個不同元素的數(shù)組進行排序,快速排序需要O(n log n)的預(yù)期時間,推導(dǎo)很枯燥就不羅嗦了。

其他排序算法

圖片來自wikipedia:

注:快排不需要額外的緩沖區(qū)開銷,但是需要棧開銷,其空間復(fù)雜度為O(log n)．

這里對上表其中幾個效率相對較高的做個簡要介紹,后面如有機會再深入學(xué)習總結(jié):

Introsort內(nèi)省排序,在C++ STL中有應(yīng)用。內(nèi)省排序(英語:Introsort)是由David Musser在1997年設(shè)計的排序算法。這個排序算法首先從快速排序開始,當遞歸深度超過一定深度(深度為排序元素數(shù)量的對數(shù)值)后轉(zhuǎn)為堆排序。采用這個方法,內(nèi)省排序既能在常規(guī)數(shù)據(jù)集上實現(xiàn)快速排序的高性能,又能在最壞情況下仍保持O(n log n) 的時間復(fù)雜度。由于這兩種算法都屬于比較排序算法,所以內(nèi)省排序也是一個比較排序算法。

Timsort排序算法:是一種混合穩(wěn)定排序算法,它是從合并排序和插入排序中派生而來的,旨在對多種實際數(shù)據(jù)表現(xiàn)良好。由Tim Peters在2002年實現(xiàn),用于Python編程語言。該算法查找已排序(運行)的數(shù)據(jù)的子序列,并使用它們對其余部分進行更有效的排序。這是通過合并運行直到滿足特定條件來完成的。自2．3版以來,Timsort一直是Python的標準排序算法。還應(yīng)用在Android平臺上的Java SE 7、GNU Octave(是一個開源的類MATLAB數(shù)序軟件)、V8(開源Java script引擎)以及Swift中,用于對非原始類型的數(shù)組進行排序。

MergeSort歸并排序:在計算機科學(xué)中,是一種高效的,通用的,基于比較的排序算法。大多數(shù)實現(xiàn)產(chǎn)生穩(wěn)定的排序,這意味著相等元素的順序在輸入和輸出中是相同的。歸并排序是約翰·馮·諾伊曼(John von Neumann)在1945年發(fā)明的分而治之算法。早在1948年,Goldstine和von Neumann的報告就對自下而上的合并排序進行了詳細描述和分析。

Tournament sort:通過使用優(yōu)先級隊列來查找排序中的下一個元素,它改進了選擇排序。在原始的選擇排序中,需要O(n)個操作才能選擇n個元素中的下一個元素;在錦標賽排序中,需要進行O(log n)運算(在O(n)中建立初始錦標賽之后)。錦標賽排序是堆排序的一種變體。

樹形選擇排序又稱錦標賽排序(Tournament Sort):是一種按照錦標賽的思想進行選擇排序的方法。首先對n個記錄的關(guān)鍵字進行兩兩比較,然后在個較小者之間再進行兩兩比較,如此重復(fù),直至選出最小的記錄為止。

塊排序或塊合并排序Block sort: 它將至少兩個合并操作與插入排序組合在一起,以達到O(n log n)的位置穩(wěn)定排序。合并兩個排序的列表,A和B,等價于將A分成大小相等的塊,在特殊規(guī)則下將每個塊插入到B中,并合并AB對。

平滑排序smoothsort,是一種基于比較的排序算法。它是堆排序的一種變體,由Edsger Dijkstra于1981年發(fā)明并發(fā)布。它的時間復(fù)雜度上限是O(n log n),但它不是一個穩(wěn)定的排序。平滑排序的優(yōu)點是,如果輸入已經(jīng)排序到一定程度,那么它會更接近O(n)的時間,而堆排序的平均值是O(n log n),而不管初始排序狀態(tài)如何。

希爾排序Shellsort,也稱為Shell排序或Shell的方法,是一種就地比較排序。它可以被看作是交換排序(冒泡排序)或插入排序(插入排序)的泛化。該方法首先對彼此相距很遠的元素對進行排序,然后逐步縮小要比較的元素之間的差距。通過從相隔很遠的元素開始,它可以比簡單的最近鄰交換更快地將一些位置錯誤的元素移動到正確的位置。Donald Shell在1959年出版了第一個版本。Shellsort的運行時間很大程度上依賴于它使用的間隙序列。

算法應(yīng)用

說到排序算法復(fù)雜度,請一定要與應(yīng)用場景結(jié)合。主要需要考慮待排數(shù)據(jù)的集的尺寸,如果數(shù)據(jù)量小的時候反而是插入排序算法應(yīng)用最為廣泛;而對于海量數(shù)據(jù)場合,則應(yīng)使用漸近有效排序策略。這是什么意思呢?說白了就是常使用混合算法!主要策略是利用快速排序、堆排序或歸并排序?qū)⒄�體快速分治排序,同時對遞歸底部的小列表采用插入排序。事實上,在實際應(yīng)用中有更復(fù)雜的變體,例如在Android,Java和Python中使用的Timsort(合并排序,插入排序和其他邏輯),以及在某些C++中用的introsort(快速排序和堆排序) 在．NET中排序?qū)崿F(xiàn)。

再說白一點,在海量數(shù)據(jù)場景,利用快速排序、堆排序或歸并排序?qū)⒑Ａ繑?shù)據(jù)快速迭代成收斂的小塊,而在小塊中采用最為常見的插入排序盡快完成小塊排序,小塊中采用插入排序則可以更大程度減少遞歸深度。

總結(jié)一下

在信息時代,有海量信息需要處理,即便有非常強勁的處理器,但如沒有很好的算法,仍然無法滿足對這些信息的處理。在處理過程中,免不了要進行信息進行排序,快排在時空兩個維度的開銷都比較均衡,大量的應(yīng)用軟件、開發(fā)工具以及軟件包都基于快排做了大量的應(yīng)用。所以說快速排序改變世界,個人認為并不為過。同時對于求職面試,快速排序算法也是高頻面試主題,值得深入研究掌握。