快速排序過程

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

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

 8 25 39 52 52' 67 70 95

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

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

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

通過一趟排序將要排序的記錄分割成兩部分，一部分的關鍵字值比別一部分的所有關鍵字都小，然后再依次對前后兩部分的記錄進行快速排序，遞歸該過程，直到序列中所有記錄都是有序為止。

步驟

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

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

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

排序過程分析

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

基準52： 52 39 67 95 70 8 25 52'

基準25： 8 25 39 52 70 95 67 52‘

基準70： 8 25 39 52 52' 67 70 95

基準52‘：8 25 39 52 52' 67 70 95

算法分析

快速排序的時間復雜度與關鍵字初始序列有關。

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

以第一個數或最后一個數為基準時，當初始序列整體或局部有序時，快速排序的性能會下降。若整體有序，此時，每次劃分只能分出一個元素，具有最壞時間復雜度，快速排序將退化成冒泡排序。

最好時間復雜度：

每次選取的基準關鍵字都是待排序列的中間值，也就是說每次劃分可以將序列劃分為長度相等的兩個序列?？焖倥判虻倪f歸過程可以用一棵二叉樹來表示，遞歸樹的高度是2為底的對數，每層需要比較的次數是n/2，所以最好時間復雜度是O(n*以2為底n的對數)，因為很多時候輸入序列都是亂序的，所以最好時間復雜度也是平均時間復雜度。

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

三種快排

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

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

2）隨機選取基準，利用隨機算法，選取待排序序列中任意一個元素作為基準。

3）三數取中，取數列中第一個數，中間位置的數，最后一個數作一個平均值作為基準。

四種優(yōu)化

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

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

2）在一次分割結束后，可以把與基準數相等的元素聚在一起，下次分割時忽略掉這些元素。

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

具本過程：

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

第二步：劃分結束后，把兩端的與基準數相等的元素移到基準數最終位置的兩側。

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

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

Partition方法在求TopK問題上的應用

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

快速排序的思想是使用一個基準元素將數組劃分成兩部分，左側都比基準數小，右側都比基準數大。

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

1）如果基準數左側元素個數Q剛好是K-1，那么在基準數左側（包含基準數本身），即為TopK的所有元素。

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

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

快排java實現

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

package sort;
public class QuickSort {
 // 暴露只一個參數的公共接口
 public void quickSort(int a[]) {
 sort(a, 0, a.length - 1);
 }
 // 快排算法的真正實現
 private void sort(int[] a, int low, int high) {
 if (low >= high)
 return;
 int i = low, j = high; // 設置這兩個變量的目的是為了保持low和high不變
 int pivotNum = a[i]; // 基準數
 while (i < j) {
 while (a[j] >= pivotNum && j > i) { // 循環(huán)結束的條件有二：一是找到比支點小的數，二是j==i
 j--;
 }
 if (j > i) { // 由于上面循環(huán)結束的功能性有兩個，對于找到比支點小的數，即j!=i，要進行位置的交換，下同
 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 + " ");
 }
 }
}

總結

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

最新評論