算法導論讀書筆記（7）

目錄

• 快速排序
• 快速排序的簡單Java實作
• 快速排序的性能
  • 最壞情況劃分
  • 最佳情況劃分
• 快速排序的随機化版本
• 比較排序

快速排序

快速排序是一種原地排序算法，對包含 n 個數的輸入數組，最壞情況運作時間為 Θ ( n2 )。雖然這個最壞情況運作時間比較差，但快速排序通常是用于排序的最佳的實用選擇。這是因為其平均性能相當好：期望的運作時間為 Θ ( n lg n )，且 Θ ( n lg n )記号中隐含的常數因子很小。

像合并排序一樣，快速排序也是基于分治模式的。下面是對一個子數組 A [ p .. r ]排序的分治過程的三個步驟：

分解：

數組 A [ p .. r ]被劃分成兩個（可能為空）子數組 A [ p .. q - 1 ]和 A [ q + 1 .. r ]，使得 A [ p .. q - 1 ]中的每一個元素都小于等于 A [ q ]，而且，小于等于 A [ q + 1 .. r ]中的元素。下标 q 也在這個劃分過程中計算。

解決：

通過遞歸調用快速排序，對子數組 A [ p .. q - 1 ]和 A [ q + 1 .. r ]排序。

合并：

因為兩個子數組是就地排序的，将它們合并不需要操作，整個數組 A [ p .. r ]已排序。

下面的過程實作了快速排序：

QUICK-SORT(A, p, r)
1 if p < r
2     q = PARTITION(A, p, r)
3     QUICK-SORT(A, p, q - 1)
4     QUICK-SORT(A, q + 1, r)
      

快速排序算法的關鍵是

PARTITION

過程，它對子數組 A [ p .. r ]進行就地重排：

PARTITION(A, p, r)
1 x = A[r]
2 i = p - 1
3 for j = p to r - 1
4     if A[j] <= x
5         i = i + 1
6         exchange A[i] with A[j]
7 exchange A[i + 1] with A[r]
8 return i + 1
      

PARTITION

總是選擇一個 x = A [ r ]作為 主元 （pivot element），并圍繞它來劃分子數組。在第3行到第6行中循環的每一輪疊代開始時，對于任何數組下标 k ，有

1. 如果 p <= k <= i ，則 A [ k ] <= x
2. 如果 i + 1 <= k <= j - 1，則 A [ k ] > x
3. 如果 k = r ，則 A [ k ] = x

下圖總結了這一結構。過程

PARTITION

作用于子數組 A [ p .. r ]後得到四個區域。 A [ p .. i ]中的各個值都小于等于 x ， A [ i + 1 .. j - 1 ]中的值都大于 x ， A [ r ] = x 。 A [ j .. r - 1 ]中的值可以是任何值。

快速排序的簡單Java實作

private 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++;
            AlgorithmUtil.swap(array, i, j);
        }
    AlgorithmUtil.swap(array, i + 1, r);
    return i + 1;
}
           

/**
 * 快速排序
 */
public static void quickSort(int[] array) {
    quickSort(array, 0, array.length - 1);
}

private 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);
    }
}
           

快速排序的性能

快速排序的運作時間與劃分是否對稱有關，而後者又與選擇了哪一個元素來進行劃分有關。如果劃分是對稱的，那麼本算法從漸近意義上來講，就和歸并排序算法一樣快；如果劃分是不對稱的，那麼本算法漸近上就和插入排序一樣慢。

最壞情況劃分

快速排序的最壞情況劃分發生在劃分過程産生的兩個區域分别包含 n - 1個元素和1個0元素的時候。假設算法的每一次遞歸調用都出現了這種不對稱劃分。劃分的時間代價為 Θ ( n )。對一個大小為0的數組進行遞歸調用後，傳回 T ( 0 ) = Θ ( 1 )，故算法的運作時間為 T ( n ) = T ( n - 1 ) + Θ ( n )。最終得到解為 T ( n ) = Θ ( n2 )。

最佳情況劃分

在

PARTITION

過程可能的最平衡劃分中，一個子問題的大小為

FLOOR（n / 2）

，另一個子問題的大小為

CEIL(n / 2)

- 1。這種情況下，其運作時間的遞歸式為 T ( n ) <= 2 T ( n / 2 ) + Θ ( n )。該遞歸式的解為 T ( n ) = O ( n lg n )。

快速排序的随機化版本

随機劃分使用 随機取樣 （random sampling）的随機化技術，從子數組 A [ p .. r ]中随機選擇一個元素并與 A [ r ]互換，因為主元是随機選擇的，我們期望在平均情況下，對輸入數組的劃分能夠比較對稱。

RANDOMIZED-PARTITION(A, p, r)
1 i = RANDOM(p, r)
2 exchange A[r] with A[i]
3 return PARTITION(A, p, r)
      

比較排序

之前已經介紹了幾種能在 O ( n lg n )時間内排序 n 個數的算法。比如歸并排序，堆排序和快速排序。這些算法都有一個相同的性質：排序結果中，各元素的次序基于輸入元素間的比較。這類排序算法統稱為 比較排序 。

在一個比較排序算法中，僅用比較來确定輸入序列< a1 ， a2 ， …， an >的元素間次序。就是說，給定兩個元素 ai 和 aj ，測試 ai < aj ， ai <= aj ， ai = aj ， ai >= aj 或 ai > aj 中的哪一個成立，以确定 ai 和 aj 之間的相對次序。

比較排序可以被抽象地視為 決策樹 。一棵決策樹是一棵滿二叉樹，表示某排序算法作用于給定輸入所做的所有比較，而控制結構，資料移動等都被忽略了。下圖是插入排序作用于含三個元素的輸入序列上的決策樹。

在決策樹中，對每個内結點都注明 i ： j ，其中1 <= i ， j <= n ， n 是輸入序列中的元素個數。對每個葉結點都注明排列< π ( 1 )， π ( 2 )， …， π （ n ）>。排序算法的執行對應于周遊一條從樹根到葉結點的路徑。在每個内結點處都要做比較。當到達一個葉結點是，排序算法就确定了順序。要使排序算法能正确地工作，其必要條件是， n 個元素的 n! 中排列中的每一種都要作為決策樹的一個葉子出現。

轉載于:https://www.cnblogs.com/sungoshawk/p/3635635.html