舉栗子分析:

分成三塊了,再遞歸子塊迭代,直到right<=left.

算法分析

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

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

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

• 具體運(yùn)行時(shí)間對(duì)不同特性的待排數(shù)據(jù)，其結(jié)果差異比較大，來(lái)看一下最好、最壞以及平均情況分析。

最差情況

• 當(dāng)待排數(shù)據(jù)序列為正序或者逆序時(shí)，pivot將是在大小為n的待排塊時(shí)中的最小（或最大）元素時(shí)。則階段1迭代中生成一個(gè)空子塊、pivot,及一個(gè)大小(n-1)的子塊,則時(shí)間復(fù)雜度為θ(n)
• 遞歸方程：

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

最好情況

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

• 遞歸方程：

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

平均情況

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

其他排序算法

注：快排不需要額外的緩沖區(qū)開(kāi)銷(xiāo)，但是需要棧開(kāi)銷(xiāo)，其空間復(fù)雜度為O(log n).

這里對(duì)上表其中幾個(gè)效率相對(duì)較高的做個(gè)簡(jiǎn)要介紹，后面如有機(jī)會(huì)再深入學(xué)習(xí)總結(jié)：

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

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

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

• Tournament sort：通過(guò)使用優(yōu)先級(jí)隊(duì)列來(lái)查找排序中的下一個(gè)元素，它改進(jìn)了選擇排序。在原始的選擇排序中，需要O（n）個(gè)操作才能選擇n個(gè)元素中的下一個(gè)元素；在錦標(biāo)賽排序中，需要進(jìn)行O（log n）運(yùn)算（在O（n）中建立初始錦標(biāo)賽之后）。錦標(biāo)賽排序是堆排序的一種變體。

• 樹(shù)形選擇排序又稱(chēng)錦標(biāo)賽排序（Tournament Sort）：是一種按照錦標(biāo)賽的思想進(jìn)行選擇排序的方法。首先對(duì)n個(gè)記錄的關(guān)鍵字進(jìn)行兩兩比較，然后在 個(gè)較小者之間再進(jìn)行兩兩比較，如此重復(fù)，直至選出最小的記錄為止。

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

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

• 希爾排序Shellsort，也稱(chēng)為Shell排序或Shell的方法，是一種就地比較排序。它可以被看作是交換排序(冒泡排序)或插入排序(插入排序)的泛化。該方法首先對(duì)彼此相距很遠(yuǎn)的元素對(duì)進(jìn)行排序，然后逐步縮小要比較的元素之間的差距。通過(guò)從相隔很遠(yuǎn)的元素開(kāi)始，它可以比簡(jiǎn)單的最近鄰交換更快地將一些位置錯(cuò)誤的元素移動(dòng)到正確的位置。Donald Shell在1959年出版了第一個(gè)版本。Shellsort的運(yùn)行時(shí)間很大程度上依賴(lài)于它使用的間隙序列。

算法應(yīng)用

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

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

總結(jié)一下

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