快速排序是運(yùn)用了分治思想的排序方式，具有O(NlogN)的平均時(shí)間復(fù)雜度，極端情況下時(shí)間復(fù)雜度為O(N^2)，跟冒泡排序一樣，但是快排的實(shí)際效率遠(yuǎn)比最壞情況好很多。它的關(guān)鍵部分是一輪劃分（由Partition()函數(shù)完成），每一輪劃分會(huì)導(dǎo)致序列中的元素分成兩部分，一部分比參照數(shù)小，一部分比參照數(shù)大。函數(shù)QSort()通過不斷調(diào)用Partition()完成給定序列的排序，當(dāng)排序序列細(xì)化為1個(gè)元素時(shí)，排序也就完成了，因?yàn)閱蝹€(gè)元素是有序的。
算法描述如下：

上面的Partition()存在很有必要優(yōu)化的地方
我們先來看幾個(gè)例子：
如果執(zhí)行Partition()前的序列是:
10 5 6 3 2 7
用第一個(gè)元素做參照（上面說的t），我們發(fā)現(xiàn)后面所有的元素都小于t，因此i后一直向后找，直到找到最后一個(gè)元素；而j一次就找到了<= t 的元素，也就是最后一個(gè)元素。這樣，while(1)結(jié)束了，Partition()執(zhí)行之后，原序列變成：
5 6 3 2 7 10
如果執(zhí)行Partition()前的序列是:
10 14 15 16 20
用第一個(gè)元素做參照（上面說的t），我們發(fā)現(xiàn)后面所有的元素都大于t，因此i一次就找到了 >= t的元素；而j一直向前找，直到找到第一個(gè)元素；這樣，while(1)結(jié)束了,Partition()執(zhí)行之后，原序列不變，仍然是：
10 14 15 16 20
上面這兩種情況都是我們不愿看到的，因?yàn)樗鼘?dǎo)致Partition()執(zhí)行后，兩邊的元素很不平均，極端情況下（比如，原序列是已排好序的），快排的時(shí)間復(fù)雜度是O(N^2)，跟冒泡排序一樣。為了避免這種情況出現(xiàn)，我們可以采用隨機(jī)化的策略，即不老是選擇第一個(gè)元素做參照，為達(dá)到這一目的，可以提前將后面的任意一個(gè)元素與第一個(gè)元素交換。
優(yōu)化后的算法為：


接下來我們在快速排序中劃分函數(shù)Partition()的基礎(chǔ)上講解一下線性時(shí)間選擇問題。所謂線性時(shí)間就是在平均O(N)的時(shí)間內(nèi)找出無序序列中第k大的元素。先排序再找出該元素是比較容易想到的方法，但排序所花的時(shí)間很可能超過O(N)（比如，快排、堆排的時(shí)間復(fù)雜度都是O(NlogN)，選擇排序、插入排序以及冒泡排序時(shí)間復(fù)雜度是O(N^2)）。
其實(shí)結(jié)合Partition()函數(shù)完成的一次劃分我們很容易想到，選擇第k大的元素不一定要排序原序列，因?yàn)榻?jīng)過一次劃分，原序列以參照數(shù)t為基準(zhǔn)被分成了兩部分，我們要找的第k大的數(shù)要么就是t，要么在t左邊，要么在t右邊，因此每次迭代我們只需要考慮原序列接近1/2的數(shù)字就行了。顯然，Select()函數(shù)的效率跟Partition()的好壞有直接關(guān)系，最壞情況下，Select()函數(shù)的時(shí)間復(fù)雜度仍為O(N^2)。
算法描述如下：
上面兩種描述略有不同，前面是我寫的，后面一個(gè)是書上的。這兩種算法都忽略了一個(gè)問題，那就是沒有考慮非法情況，即要選擇的數(shù)超出了原有序列，比如原序列只有n個(gè)數(shù)，而卻讓找出第n+1大的數(shù)。