快速排序的深度解讀

快速排序通過(guò)一趟排序?qū)⒋判蛄蟹指畛瑟?dú)立的兩部分，其中一部分序列的關(guān)鍵字均比另一部分序列的關(guān)鍵字小，則可分別對(duì)這兩部分序列繼續(xù)進(jìn)行排序，以達(dá)到整個(gè)序列有序的目的。

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

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

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

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

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

算法圖解

問(wèn)題解疑

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

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

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

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

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

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

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

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

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