快速排序算法

2019-11-06 06:31:52

字體：大中小

來源：轉載

供稿：網友

快速排序算法通常是用于排序的最佳選擇，盡管它在最壞情況下的運行時間是O(n2)，但平均性能是O(nlgn)，并且邏輯簡單。快速排序算法一共有兩個子過程

Partition(int[] array,int p,int r)，它把數組的p至r部分就地重排，并返回一個q，并且使數組滿足以下條件：q左邊的數值全部小于或等于q的數值，q右邊的數值都大于或等于q的數值。QuickSort(int[] array,int p,int r)，它會巧妙地調用Partition函數，以及遞歸調用自身，最終完成對數組array的排序。

下面首先來看以下Partition函數

static int Partition(int[] array, int p, int r){ int x = array[r]; int i = p - 1; for (int j = p; j < r; j++) { if (array[j] < x) { i++; //exchange array[i] and array[j] int temp = array[i]; array[i] = array[j]; array[j] = temp; } } //exchange array[i+1] and array[r] int temp2 = array[i + 1]; array[i + 1] = array[r]; array[r] = temp2; return i + 1;}

假設輸入的數組arrray為7, 2, 101, 15, 1, 6, 21，那么調用Partition(array, 0, 6)的話，會返回5，并且數組被修改為7, 2, 15, 1, 6, 21, 101?？梢钥闯鰜?，排序后的數組的索引位置為5的值是21，在此之前的所有數字都小于或等于21，在此之后的所有數字都大于等于21。

接下來看看QuickSort函數

static void QuickSort(int[] array, int p, int r){ if (p < r) { int q = Partition(array, p, r); QuickSort(array, p, q -1); QuickSort(array, q + 1, r); }}

QuickSort函數在調用Partition函數之后，獲取到一個q值，這個q在數組中的位置已經是正確的了，所以，無需再對q位置的數組進行排序，所以會遞歸調用兩次QuickSort，第一次調用的最后一個參數是q-1，第二次調用的最后一個參數是q+1。知道p>=r，說明整個數組的所有位置都已經正確的排序了。

下面是main函數

static void Main(string[] args){ int[] array = { 7, 2, 101, 15, 1, 6, 21 }; QuickSort(array, 0, array.Length - 1);}

上一篇：POJ1251 Jungle Roads(最小生成樹，Kruskal)

下一篇：多線程（基本知識）