快速排序通過一趟排序?qū)⒋判蛄蟹指畛瑟毩⒌膬刹糠郑渲幸徊糠中蛄械年P(guān)鍵字均比另一部分序列的關(guān)鍵字小，則可分別對這兩部分序列繼續(xù)進(jìn)行排序，以達(dá)到整個序列有序的目的。

快速排序的基本思想是采用分治法(Divide and Conquer)來將一個數(shù)組排序。它選擇一個元素作為“基準(zhǔn)”(pivot)，通過一趟排序?qū)⒋判虻臄?shù)據(jù)分割成獨立的兩部分，其中一部分的所有數(shù)據(jù)都比基準(zhǔn)小，另一部分的所有數(shù)據(jù)都比基準(zhǔn)大，然后再按此方法對這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個排序過程可以遞歸進(jìn)行，以此達(dá)到整個數(shù)據(jù)變成有序序列。

快速排序詳細(xì)的執(zhí)行步驟如下：

從序列中挑出一個元素，稱為 “基準(zhǔn)”(pivot);

重新排序序列，所有比基準(zhǔn)值小的元素擺放在基準(zhǔn)前面，所有比基準(zhǔn)值大的元素擺在基準(zhǔn)的后面(相同的數(shù)可以到任一邊)。在這個分區(qū)退出之后，該基準(zhǔn)就處于序列的中間位置。這個稱為分區(qū)(partition)操作;

遞歸地(recursive)把小于基準(zhǔn)值元素的子序列和大于基準(zhǔn)值元素的子序列排序。

算法圖解

問題解疑

快速排序可以怎樣選擇基準(zhǔn)值?

第一種方式：固定位置選擇基準(zhǔn)值;在整個序列已經(jīng)趨于有序的情況下，效率很低。

第二種方式：隨機(jī)選取待排序列中任意一個數(shù)作為基準(zhǔn)值;當(dāng)該序列趨于有序時，能夠讓效率提高，但在整個序列數(shù)全部相等的時候，隨機(jī)快排的效率依然很低。

第三種方式：從區(qū)間的首、尾、中間，分別取出一個數(shù)，然后對比大小，取這 3 個數(shù)的中間值作為基準(zhǔn)值;這種方式解決了很多特殊的問題，但對于有很多重復(fù)值的序列，效果依然不好。

快速排序有什么好的優(yōu)化方法?

首先，合理選擇基準(zhǔn)值，將固定位置選擇基準(zhǔn)值改成三點取中法，可以解決很多特殊的情況，實現(xiàn)更快地分區(qū)。

其次，當(dāng)待排序序列的長度分割到一定大小后，使用插入排序。對于待排序的序列長度很小或基本趨于有序時，插入排序的效率更好。

在排序后，可以將與基準(zhǔn)值相等的數(shù)放在一起，在下次分割時可以不考慮這些數(shù)。對于解決重復(fù)數(shù)據(jù)較多的情況非常有用。

在實現(xiàn)上，遞歸實現(xiàn)的快速排序在函數(shù)尾部有兩次遞歸操作，可以對其使用尾遞歸優(yōu)化(簡單地說，就是尾位置調(diào)用自身)。