看動畫學算法之:排序-快速排序

目錄

• 簡介
• 快速排序的例子
• 快速排序的java代碼實作
• 随機快速排序的java實作
• 快速排序的時間複雜度

快速排序也采用的是分而制之的思想。那麼快速排序和歸并排序的差別在什麼地方呢？

歸并排序是将所有的元素拆分成一個個排好序的數組，然後将這些數組再進行合并。

而快速排序雖然也是拆分，但是拆分之後的操作是從數組中選出一個中間節點，然後将數組分成兩部分。

左邊的部分小于中間節點，右邊的部分大于中間節點。

然後再分别處理左邊的數組合右邊的數組。

假如我們有一個數組：29,10,14,37,20,25,44,15，怎麼對它進行快速排序呢？

先看一個動畫：

我們再分析一下快速排序的步驟。

我們選擇的是最左邊的元素29作為中間點元素，然後将數組分成三部分：[0, 14, 15, 20, 25],[29],[44, 37]。

中間節點29已經排好序了，不需要處理。

接下來我們再對左右分别進行快速排序。最後就得到了一個所有元素都排序的數組。

我們先來看最核心的部分partition，如何将數組以中間節點為界，分成左右兩部分呢？

我們的最終結果，是要将array分割成為三部分。

首先我們選擇最左側的元素作為中間節點的值。然後周遊數組中的其他元素。

假如m=middleIndex，k=要周遊的元素index

考慮兩種情況，第一種情況是數組中的元素比中間節點的值要大。

這種情況下，m不需要移動，k+1繼續周遊即可。

第二種情況下，數組中的元素比中間節點的值要小。

因為m左邊的元素都要比中間節點的值要小，是以這種情況下m需要+1，即右移一位。

現在m+1位置的元素要麼還沒有進行比較，要麼就是比中間節點的值要大，我們可以巧妙的将m+1位置的元素和k位置的元素互換位置，這樣仍然能夠保證m左側的元素要比中間節點的值要小。

将上面的分析總結成java代碼如下：

private int partition(int[] array, int i, int j) {             //選擇最左側的元素作為中心點,middleValue就是中心點的值             int middleValue = array[i];             int middleIndex = i;             //從i+1周遊整個數組             for (int k = i+1; k <= j; k++) {                 //如果數組元素小于middleValue，表示middleIndex需要右移一位                 //右移之後，我們需要将小于middleValue的array[k]移動到middleIndex的左邊，                 // 最簡單的辦法就是交換k和middleIndex的值                 if (array[k] < middleValue) {                     middleIndex++;                     //交換數組的兩個元素                     swap(array, k , middleIndex);                 } //如果數組元素大于等于middleValue,則繼續向後周遊,middleIndex值不變             }             // 最後将中心點放入middleIndex位置             swap(array, i, middleIndex);             return middleIndex;         }           

最後我們需要将最左側的元素和中間節點應該在的index的元素互換下位置，這樣就将中間節點移動到了中間位置，并傳回中間位置。

再來看下divide的代碼：

public void doQuickSort(int[] array, int low, int high) {             //遞歸的結束條件             if (low < high) {                 //找出中心節點的值                 int middleIndex = partition(array, low, high);                 //數組分成了三部分：                 // a[low..high] ~> a[low..m–1], pivot, a[m+1..high]                 //遞歸周遊左側部分                 doQuickSort(array, low, middleIndex-1);                 // a[m] 是中心節點，已經排好序了，不需要繼續周遊                 //遞歸周遊右側部分                 doQuickSort(array, middleIndex+1, high);                 log.info("QuickSort之後的數組:{}",array);             }         }           

divide的代碼就很簡單了，找到中間節點的位置之後，我們再分别周遊數組的左右兩邊即可。最後得到排好序的數組。

上面的例子中，我們的中間節點的選擇是數組的最左元素，為了保證排序的效率，我們可以從數組中随機選擇一個元素來作為中間節點。

private int partition(int[] array, int i, int j) {             //随機選擇一個元素作為中心點,middleValue就是中心點的值             int randomIndex=i+new Random().nextInt(j-i);             log.info("randomIndex:{}",randomIndex);             //首先将randomIndex的值和i互換位置,就可以複用QuickSort的邏輯             swap(array, i , randomIndex);             int middleValue = array[i];             int middleIndex = i;             //從i周遊整個數組             for (int k = i+1; k <= j; k++) {                 //如果數組元素小于middleValue，表示middleIndex需要右移一位                 //右移之後，我們需要将小于middleValue的array[k]移動到middleIndex的左邊，                 // 最簡單的辦法就是交換k和middleIndex的值                 if (array[k] < middleValue) {                     middleIndex++;                     //交換數組的兩個元素                     swap(array, k , middleIndex);                 } //如果數組元素大于等于middleValue,則繼續向後周遊,middleIndex值不變             }             // 最後将中心點放入middleIndex位置             swap(array, i, middleIndex);             return middleIndex;         }           

上面的代碼，我們在分區的時候，先選擇出一個随機的節點，然後将這個随機的節點和最左側的元素交換位置，後面的代碼就可以重用上面的QuickSort的代碼邏輯了。

從上面的分析我們可以看出，每次分區的時間複雜度應該是O(N)，而divide又近似二分法，是以總的時間複雜度是O(N logN)。

本文的代碼位址：

learn-algorithm

本文作者：flydean程式那些事

本文連結：http://www.flydean.com/algorithm-quick-sort/

本文來源：flydean的部落格

歡迎關注我的公衆号:程式那些事，更多精彩等着您！