快速排序過程

沒有既不浪費(fèi)空間又可以快一點(diǎn)的排序算法呢？那就是“快速排序”！光聽這個名字是不是就覺得很高端呢。

假設(shè)我們現(xiàn)在對“52 39 67 95 70 8 25 52'”這個8個數(shù)進(jìn)行排序。首先在這個序列中隨便找一個數(shù)作為基準(zhǔn)數(shù)（不要被這個名詞嚇到了，就是一個用來參照的數(shù)，待會你就知道它用來做啥的了）。為了方便，就讓第一個數(shù)70作為基準(zhǔn)數(shù)吧。接下來，需要將這個序列中所有比基準(zhǔn)數(shù)大的數(shù)放在70的右邊，比基準(zhǔn)數(shù)小的數(shù)放在70的左邊，類似下面這種排列：

 8 25 39 52 52' 67 70 95

在初始狀態(tài)下，數(shù)字70在序列的第5位。我們的目標(biāo)是將70挪到序列中間的某個位置，假設(shè)這個位置是k?，F(xiàn)在就需要尋找這個k，并且以第k位為分界點(diǎn)，左邊的數(shù)都小于等于70，右邊的數(shù)都大于等于70。想一想，你有辦法可以做到這點(diǎn)嗎？

基本思想是分治的思想,說到分治，就應(yīng)該想到和遞歸是分不開的。

有些書上會使用關(guān)鍵字比較的表述，有些書上會直接使用記錄比較表述，這兩種說法是兩個維度上的說法。這里序列元素的關(guān)鍵字屬于記錄的一部分，為了簡化問題，本文的討論并不區(qū)分關(guān)鍵字和記錄，代碼實(shí)現(xiàn)中使用整數(shù)來表示記錄。簡而言之，本文的討論簡化為，對整型數(shù)組的快速排序。

通過一趟排序?qū)⒁判虻挠涗浄指畛蓛刹糠?，一部分的關(guān)鍵字值比別一部分的所有關(guān)鍵字都小，然后再依次對前后兩部分的記錄進(jìn)行快速排序，遞歸該過程，直到序列中所有記錄都是有序?yàn)橹埂?/p>

步驟

1）分解。選擇第一個元素作為基準(zhǔn)數(shù)，將輸入序列array[m…n]劃分成兩個非空序列array[m…k]和array[k+1…n],使array[m…k]中任一元素的值不大于array[k+1…n]任一元素值。

2）遞歸求解。通過遞歸調(diào)用快排算法分別對array[m…k]和array[k+1…n]進(jìn)行排序

3）合并。由于對分解出的兩個子序列排序都是原地進(jìn)行的,所以在array[m…k]和array[k+1…n]都排好序后不需要再執(zhí)行任何計(jì)算，就能將array[m…n]排好序。因此這一步是不需要在程序中體現(xiàn)的。

排序過程分析

初始關(guān)鍵字：52 39 67 95 70 8 25 52' ，下面將列出每一趟執(zhí)行的結(jié)果。

基準(zhǔn)52： 52 39 67 95 70 8 25 52'

基準(zhǔn)25： 8 25 39 52 70 95 67 52‘

基準(zhǔn)70： 8 25 39 52 52' 67 70 95

基準(zhǔn)52‘：8 25 39 52 52' 67 70 95

算法分析

快速排序的時間復(fù)雜度與關(guān)鍵字初始序列有關(guān)。

最壞時間復(fù)雜度：O(n^2):

以第一個數(shù)或最后一個數(shù)為基準(zhǔn)時，當(dāng)初始序列整體或局部有序時，快速排序的性能會下降。若整體有序，此時，每次劃分只能分出一個元素，具有最壞時間復(fù)雜度，快速排序?qū)⑼嘶擅芭菖判颉?/p>

最好時間復(fù)雜度：

每次選取的基準(zhǔn)關(guān)鍵字都是待排序列的中間值，也就是說每次劃分可以將序列劃分為長度相等的兩個序列。快速排序的遞歸過程可以用一棵二叉樹來表示，遞歸樹的高度是2為底的對數(shù)，每層需要比較的次數(shù)是n/2，所以最好時間復(fù)雜度是O(n*以2為底n的對數(shù))，因?yàn)楹芏鄷r候輸入序列都是亂序的，所以最好時間復(fù)雜度也是平均時間復(fù)雜度。

三種快排和四種優(yōu)化方法

三種快排

這里區(qū)分的方式是不同基準(zhǔn)的選擇方法：

1）固定位置，取第一個或最后一個元素作為基準(zhǔn)。這種選取方法不合適局部有序的輸入。

2）隨機(jī)選取基準(zhǔn)，利用隨機(jī)算法，選取待排序序列中任意一個元素作為基準(zhǔn)。

3）三數(shù)取中，取數(shù)列中第一個數(shù)，中間位置的數(shù)，最后一個數(shù)作一個平均值作為基準(zhǔn)。

四種優(yōu)化

1）當(dāng)排序序列長度分割到一定程度時，使用插入排序

對于N很小或局部有序的數(shù)組，直接插入排序的效率非常高。

2）在一次分割結(jié)束后，可以把與基準(zhǔn)數(shù)相等的元素聚在一起，下次分割時忽略掉這些元素。

對于含有重復(fù)元素比較多的序列，這種優(yōu)化方法效果比較好，可以減少很多跌代次數(shù)。

具本過程：

第一步：在劃分過程，把與所選取的基準(zhǔn)數(shù)相等的元素放在數(shù)組的兩端。

第二步：劃分結(jié)束后，把兩端的與基準(zhǔn)數(shù)相等的元素移到基準(zhǔn)數(shù)最終位置的兩側(cè)。

3）優(yōu)化遞歸操作。

4）使用多線程并行處理子劃分。

Partition方法在求TopK問題上的應(yīng)用

TopK問題即求序列中最大或最小的K個數(shù)。這里以求最小K個數(shù)為例。

快速排序的思想是使用一個基準(zhǔn)元素將數(shù)組劃分成兩部分，左側(cè)都比基準(zhǔn)數(shù)小，右側(cè)都比基準(zhǔn)數(shù)大。

給定數(shù)組array[low…h(huán)igh],一趟快排劃分后的結(jié)果有三種：

1）如果基準(zhǔn)數(shù)左側(cè)元素個數(shù)Q剛好是K-1，那么在基準(zhǔn)數(shù)左側(cè)（包含基準(zhǔn)數(shù)本身），即為TopK的所有元素。

2）如果基準(zhǔn)數(shù)左側(cè)元素個數(shù)Q小于K-1,那么說明基準(zhǔn)數(shù)左側(cè)的Q個數(shù)都是TopK里的元素，只需要在基準(zhǔn)數(shù)的右側(cè)找出剩下的K-Q個元素即可。問題轉(zhuǎn)化成了以基準(zhǔn)數(shù)下標(biāo)為起點(diǎn)，高位(high)為終點(diǎn)的Top(K-Q)。遞歸下去即可。

3）如果基準(zhǔn)數(shù)左側(cè)元素個數(shù)Q大于K-1,說明第K個位置，在基準(zhǔn)數(shù)的左側(cè)，需要縮小搜索范圍，在低位(low)至基準(zhǔn)數(shù)位置重復(fù)遞歸即可，最終問題會轉(zhuǎn)化成上面兩種情況。

快排java實(shí)現(xiàn)

在手寫快排算法時，最好先把一趟排序的過程寫出來。

package sort;
public class QuickSort {
 // 暴露只一個參數(shù)的公共接口
 public void quickSort(int a[]) {
 sort(a, 0, a.length - 1);
 }
 // 快排算法的真正實(shí)現(xiàn)
 private void sort(int[] a, int low, int high) {
 if (low >= high)
 return;
 int i = low, j = high; // 設(shè)置這兩個變量的目的是為了保持low和high不變
 int pivotNum = a[i]; // 基準(zhǔn)數(shù)
 while (i < j) {
 while (a[j] >= pivotNum && j > i) { // 循環(huán)結(jié)束的條件有二：一是找到比支點(diǎn)小的數(shù)，二是j==i
 j--;
 }
 if (j > i) { // 由于上面循環(huán)結(jié)束的功能性有兩個，對于找到比支點(diǎn)小的數(shù)，即j!=i，要進(jìn)行位置的交換，下同
 a[i] = a[j];
 i++;
 }
 while (a[i] < pivotNum && i < j) { 
 i++;
 }
 if (i < j) {
 a[j] = a[i];
 j--;
 }
 }
 a[i] = pivotNum;
 sort(a, low, i - 1);
 sort(a, i + 1, high);
 }
 public static void main(String[] args) {
 int[] a = { 52, 39, 67, 95, 70, 8, 25, 52 };
 new QuickSort().quickSort(a);
 for (int i : a) {
 System.out.print(i + " ");
 }
 }
}

總結(jié)

以上就是這篇文章的全部內(nèi)容了，希望本文的內(nèi)容對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，謝謝大家對腳本之家的支持。如果你想了解更多相關(guān)內(nèi)容請查看下面相關(guān)鏈接

最新評論