要點(diǎn)

快速排序是一種交換排序。

快速排序由C. A. R. Hoare在1962年提出。

它的基本思想是：通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分：分割點(diǎn)左邊都是比它小的數(shù)，右邊都是比它大的數(shù)。

然后再按此方法對(duì)這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個(gè)排序過程可以遞歸進(jìn)行，以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列。

詳細(xì)的圖解往往比大堆的文字更有說明力，所以直接上圖：

上圖中，演示了快速排序的處理過程：

初始狀態(tài)為一組無(wú)序的數(shù)組：2、4、5、1、3。

經(jīng)過以上操作步驟后，完成了第一次的排序，得到新的數(shù)組：1、2、5、4、3。

新的數(shù)組中，以2為分割點(diǎn)，左邊都是比2小的數(shù)，右邊都是比2大的數(shù)。

因?yàn)?已經(jīng)在數(shù)組中找到了合適的位置，所以不用再動(dòng)。

2左邊的數(shù)組只有一個(gè)元素1，所以顯然不用再排序，位置也被確定。（注：這種情況時(shí)，left指針和right指針顯然是重合的。因此在代碼中，我們可以通過設(shè)置判定條件left必須小于right，如果不滿足，則不用排序了）。

而對(duì)于2右邊的數(shù)組5、4、3，設(shè)置left指向5，right指向3，開始繼續(xù)重復(fù)圖中的一、二、三、四步驟，對(duì)新的數(shù)組進(jìn)行排序。

核心代碼

publicintdivision(int[]list,intleft,intright){//以最左邊的數(shù)(left)為基準(zhǔn)intbase=list[left];while(left=base)right--;//找到了比base小的元素，將這個(gè)元素放到最左邊的位置list[left]=list[right];//從序列左端開始，向右遍歷，直到找到大于base的數(shù)while(left

快速排序算法的性能

時(shí)間復(fù)雜度

當(dāng)數(shù)據(jù)有序時(shí)，以第一個(gè)關(guān)鍵字為基準(zhǔn)分為兩個(gè)子序列，前一個(gè)子序列為空，此時(shí)執(zhí)行效率最差。

而當(dāng)數(shù)據(jù)隨機(jī)分布時(shí)，以第一個(gè)關(guān)鍵字為基準(zhǔn)分為兩個(gè)子序列，兩個(gè)子序列的元素個(gè)數(shù)接近相等，此時(shí)執(zhí)行效率最好。

所以，數(shù)據(jù)越隨機(jī)分布時(shí)，快速排序性能越好；數(shù)據(jù)越接近有序，快速排序性能越差。

空間復(fù)雜度

快速排序在每次分割的過程中，需要 1 個(gè)空間存儲(chǔ)基準(zhǔn)值。而快速排序的大概需要 Nlog2N次的分割處理，所以占用空間也是 Nlog2N 個(gè)。

算法穩(wěn)定性

在快速排序中，相等元素可能會(huì)因?yàn)榉謪^(qū)而交換順序，所以它是不穩(wěn)定的算法。

完整參考代碼

JAVA版本

代碼實(shí)現(xiàn)

1publicclassQuickSort{23publicintdivision(int[]list,intleft,intright){4//以最左邊的數(shù)(left)為基準(zhǔn)5intbase=list[left];6while(left=base)9right--;10//找到了比base小的元素，將這個(gè)元素放到最左邊的位置11list[left]=list[right];1213//從序列左端開始，向右遍歷，直到找到大于base的數(shù)14while(left

運(yùn)行結(jié)果

排序前: 1 3 4 5 2 6 9 7 8 0 base = 1: 0 1 4 5 2 6 9 7 8 3 base = 4: 3 2 4 6 9 7 8 5 base = 3: 2 3 base = 6: 5 6 7 8 9 base = 7: 7 8 9 base = 8: 8 9 排序后: 0 1 2 3 4 5 6 7 8 9