Java排序算法總結(jié)（七）：快速排序
快速排序（Quicksort）是對(duì)冒泡排序的一種改進(jìn)。它的基本思想是：通過(guò)一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對(duì)這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個(gè)排序過(guò)程可以遞歸進(jìn)行，以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列?？焖倥判虿环€(wěn)定，O(log(n))的額外空間，時(shí)間復(fù)雜度為O(nlog(n))，不是自適應(yīng)的。
快速排序(Quicksort)有幾個(gè)值得一提的變種算法，這里進(jìn)行一些簡(jiǎn)要介紹：
隨機(jī)化快排：快速排序的最壞情況基于每次劃分對(duì)主元的選擇?；镜目焖倥判蜻x取第一個(gè)元素作為主元。這樣在數(shù)組已經(jīng)有序的情況下，每次劃分將得到最壞的結(jié)果。一種比較常見的優(yōu)化方法是隨機(jī)化算法，即隨機(jī)選取一個(gè)元素作為主元。這種情況下雖然最壞情況仍然是O(n^2)，但最壞情況不再依賴于輸入數(shù)據(jù)，而是由于隨機(jī)函數(shù)取值不佳。實(shí)際上，隨機(jī)化快速排序得到理論最壞情況的可能性僅為1/(2^n)。所以隨機(jī)化快速排序可以對(duì)于絕大多數(shù)輸入數(shù)據(jù)達(dá)到O(nlogn)的期望時(shí)間復(fù)雜度。一位前輩做出了一個(gè)精辟的總結(jié)：“隨機(jī)化快速排序可以滿足一個(gè)人一輩子的人品需求。”
隨機(jī)化快速排序的唯一缺點(diǎn)在于，一旦輸入數(shù)據(jù)中有很多的相同數(shù)據(jù)，隨機(jī)化的效果將直接減弱。對(duì)于極限情況，即對(duì)于n個(gè)相同的數(shù)排序，隨機(jī)化快速排序的時(shí)間復(fù)雜度將毫無(wú)疑問(wèn)的降低到O(n^2)。解決方法是用一種方法進(jìn)行掃描，使沒(méi)有交換的情況下主元保留在原位置。
平衡快排（Balanced Quicksort）：每次盡可能地選擇一個(gè)能夠代表中值的元素作為關(guān)鍵數(shù)據(jù)，然后遵循普通快排的原則進(jìn)行比較、替換和遞歸。通常來(lái)說(shuō)，選擇這個(gè)數(shù)據(jù)的方法是取開頭、結(jié)尾、中間3個(gè)數(shù)據(jù)，通過(guò)比較選出其中的中值。取這3個(gè)值的好處是在實(shí)際問(wèn)題（例如信息學(xué)競(jìng)賽……）中，出現(xiàn)近似順序數(shù)據(jù)或逆序數(shù)據(jù)的概率較大，此時(shí)中間數(shù)據(jù)必然成為中值，而也是事實(shí)上的近似中值。萬(wàn)一遇到正好中間大兩邊?。ɑ蚍粗┑臄?shù)據(jù)，取的值都接近最值，那么由于至少能將兩部分分開，實(shí)際效率也會(huì)有2倍左右的增加，而且利于將數(shù)據(jù)略微打亂，破壞退化的結(jié)構(gòu)。
外部快排（External Quicksort）：與普通快排不同的是，關(guān)鍵數(shù)據(jù)是一段buffer，首先將之前和之后的M/2個(gè)元素讀入buffer并對(duì)該buffer中的這些元素進(jìn)行排序，然后從被排序數(shù)組的開頭（或者結(jié)尾）讀入下一個(gè)元素，假如這個(gè)元素小于buffer中最小的元素，把它寫到最開頭的空位上；假如這個(gè)元素大于buffer中最大的元素，則寫到最后的空位上；否則把buffer中最大或者最小的元素寫入數(shù)組，并把這個(gè)元素放在buffer里。保持最大值低于這些關(guān)鍵數(shù)據(jù)，最小值高于這些關(guān)鍵數(shù)據(jù)，從而避免對(duì)已經(jīng)有序的中間的數(shù)據(jù)進(jìn)行重排。完成后，數(shù)組的中間空位必然空出，把這個(gè)buffer寫入數(shù)組中間空位。然后遞歸地對(duì)外部更小的部分，循環(huán)地對(duì)其他部分進(jìn)行排序。
三路基數(shù)快排（Three-way Radix Quicksort，也稱作Multikey Quicksort、Multi-key Quicksort）：結(jié)合了基數(shù)排序（radix sort，如一般的字符串比較排序就是基數(shù)排序）和快排的特點(diǎn)，是字符串排序中比較高效的算法。該算法被排序數(shù)組的元素具有一個(gè)特點(diǎn)，即multikey，如一個(gè)字符串，每個(gè)字母可以看作是一個(gè)key。算法每次在被排序數(shù)組中任意選擇一個(gè)元素作為關(guān)鍵數(shù)據(jù)，首先僅考慮這個(gè)元素的第一個(gè)key（字母），然后把其他元素通過(guò)key的比較分成小于、等于、大于關(guān)鍵數(shù)據(jù)的三個(gè)部分。然后遞歸地基于這一個(gè)key位置對(duì)“小于”和“大于”部分進(jìn)行排序，基于下一個(gè)key對(duì)“等于”部分進(jìn)行排序。
代碼實(shí)現(xiàn)：
- public class QuickSort {
- public static void sort(Comparable[] data, int low, int high) {
- // 樞紐元,一般以第一個(gè)元素為基準(zhǔn)進(jìn)行劃分
- int i = low;
- int j = high;
- if (low < high) {
- // 從數(shù)組兩端交替地向中間掃描
- Comparable pivotKey = data[low];
- // 進(jìn)行掃描的指針i,j;i從左邊開始,j從右邊開始
- while (i < j) {
- while (i < j && data[j].compareTo(pivotKey) > 0) {
- j--;
- }// end while
- if (i < j) {
- // 比樞紐元素小的移動(dòng)到左邊
- data[i] = data[j];
- i++;
- }// end if
- while (i < j && data[i].compareTo(pivotKey) < 0) {
- i++;
- }// end while
- if (i < j) {
- // 比樞紐元素大的移動(dòng)到右邊
- data[j] = data[i];
- j--;
- }// end if
- }// end while
- // 樞紐元素移動(dòng)到正確位置
- data[i] = pivotKey;
- // 前半個(gè)子表遞歸排序
- sort(data, low, i - 1);
- // 后半個(gè)子表遞歸排序
- sort(data, i + 1, high);
- }// end if
- }// end sort
- public static void main(String[] args) {
- // 在JDK1.5版本以上,基本數(shù)據(jù)類型可以自動(dòng)裝箱
- // int,double等基本類型的包裝類已實(shí)現(xiàn)了Comparable接口
- Comparable[] c = { 4, 9, 23, 1, 45, 27, 5, 2 };
- sort(c, 0, c.length - 1);
- for (Comparable data : c) {
- System.out.println(data);
- }
- }
- }
快速排序是目前使用的最廣泛的排序算法了，快速排序的核心在于分割算法，也可以說(shuō)是最有技巧的部分。希望通過(guò)本文的介紹，能給你帶來(lái)幫助。
【編輯推薦】
- 5.11 三行代碼的快速排序
- 12.3.2 基于任務(wù)竊取的快速排序
- 19.4.2 用Parallel_For進(jìn)行并行快速排序
- C#快速排序的趣味實(shí)現(xiàn)：從Haskell說(shuō)起
