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

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


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