閱讀經(jīng)典——《算法導(dǎo)論》06
顧名思義，快速排序必然是所有排序算法中最快的一個(gè)。它的最壞情況時(shí)間復(fù)雜度是Θ(n2)，但期望時(shí)間復(fù)雜度是Θ(nlgn)，而且Θ(nlgn)中隱含的常數(shù)因子非常小。
使用隨機(jī)抽樣的快速排序算法可以避免最壞情況的發(fā)生，在元素互異的情況下，期望時(shí)間復(fù)雜度是O(nlgn)。
算法思想
與歸并排序類似，快速排序也利用了分治的思想。每一趟快速排序?qū)⒄麄€(gè)序列分成小于x的部分，x，大于x的部分。下一趟快速排序再遞歸對這幾個(gè)部分排序。
接下來簡要介紹具體的實(shí)現(xiàn)方案。排序過程中維護(hù)四個(gè)區(qū)域，如下圖所示。
每一趟快速排序之前選取最后一個(gè)數(shù)作為主元x，通過遍歷整個(gè)序列，把“無限制”區(qū)域的數(shù)放到“小于x”或“大于x”中。下圖展示了給定序列的一趟快速排序過程。
其中最后一步將主元放在了前后兩部分中間。
代碼實(shí)現(xiàn)
/**
* 使用快速排序算法對給定的數(shù)組排序
* @param arr 需要排序的數(shù)組
* @param p 指定排序區(qū)間的起始下標(biāo)
* @param r 指定排序區(qū)間的結(jié)束下標(biāo)
*/
public void quickSort(int[] arr, int p, int r) {
if (p < r) {
int q = partition(arr, p, r);
quickSort(arr, p, q - 1);
quickSort(arr, q + 1, r);
}
}
/**
* 快速排序中的一趟劃分
* @param arr 需要排序的數(shù)組
* @param p 指定排序區(qū)間的起始下標(biāo)
* @param r 指定排序區(qū)間的結(jié)束下標(biāo)
* @return 劃分后主元的位置
*/
public int partition(int[] arr, int p, int r) {
int x = arr[r];
int i = p - 1;
int temp;
for (int j = p; j < r; j++) {
if (arr[j] <= x) {
i++;
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
temp = arr[i + 1];
arr[i + 1] = arr[r];
arr[r] = temp;
return i + 1;
}
完整代碼見QuickSort.java。
性能分析
快速排序的運(yùn)行時(shí)間依賴于劃分是否平衡，而平衡與否又依賴于用于劃分的元素。在最壞情況下，極度不平衡的劃分（主元恰好是極大值或極小值）導(dǎo)致時(shí)間復(fù)雜度為Θ(n2)。比如輸入數(shù)組大部分有序的情況下，快速排序速度會很低，反而插入排序速度很快。因此需要根據(jù)實(shí)際輸入的情況選擇排序算法。
人們想出了許多方法來盡量保證劃分的平衡，比如隨機(jī)取三個(gè)元素，并用這三個(gè)元素的中位數(shù)對數(shù)組進(jìn)行劃分。但是無論怎樣，使用快速排序是有風(fēng)險(xiǎn)的，普遍的觀點(diǎn)是，如果最差情況的性能會對你的程序造成很壞的影響，還是放棄快速排序?yàn)楹谩?/p>
關(guān)于時(shí)間復(fù)雜度的具體計(jì)算，隨機(jī)化快速排序算法的漸近上界的證明，由于太過復(fù)雜難懂，我也無法完全理解，可以閱讀原文或?yàn)g覽本文文末給出了幾個(gè)鏈接，里面有更詳細(xì)的討論。
關(guān)注作者或文集《算法導(dǎo)論》，第一時(shí)間獲取最新發(fā)布文章。
獲取文集中的全套源碼請?jiān)L問GitHub代碼倉庫Algorithm。
擴(kuò)展閱讀
Engineering Quicksort tef
A Killer Adversary for Quicksort M. D. MCILROY
Why is quicksort better than other sorting algorithms in practice? A question in StackExchange
