基礎算法【5】：快速排序QuickSort

1. 快速排序：
   1. 快速排序是另一個分而治之排序算法。
   2. 我們将看到，這種确定性的，非随機化的快速排序的版本可能在對手輸入中具有O（N2）的很差的時間複雜度，之後再繼續随機化的和可用的版本。
   3. 疑問：“确定的，非随機化的”指的是什麼？指的是樞紐點的選取。
2. 快速排序是分而治之的算法：
   1. 劃分步驟：選擇一個項目 p（稱為樞軸點）然後将 a[i..j] 的項目分為三部分：a [i..m-1]，a [m] 和 a[m + 1..j]。 a [i..m-1]（可能為空）包含小于 p 的項目。 a [m] 是樞軸點 p，例如：指數 m 是已排序數組 a 的排序順序中 p 的正确位置。 a [m + 1..j]（可能為空）包含大于或等于 p 的項目。 然後，遞歸地對這兩部分進行排序。
   2. 解決步驟：不要驚訝......我們什麼都不做！
   3. 如果您将其與歸并排序進行比較，您會發現快速排序的 D＆C 步驟與歸并排序完全相反。
      1. D&C: devide & conquer, 分 and 治。
3. 重要的子程式，O(N)分區：
   1. 我們首先讨論其最重要的子程式：O（N）分區，然後解析這個快速排序算法。
   2. 要分區 a[i..j]，我們首先選擇 a[i] 作為樞紐 p。其餘項目（即a [i + 1..j]）分為3個區域：
      1. S1 = a [i + 1..m]其中項目 < p，
      2. S2 = a [m + 1..k-1]其中項目 ≥ p，且
      3. 未知的= a [k..j]，其中項目尚未配置設定給 S1 或 S2。
   3. 讨論：為什麼我們選擇 p = a [i]？ 還有其他選擇嗎？
   4. 更難的讨論：始終在S2上放置 == p的項目是好的嗎？
4. 分區排序 - 繼續：
   1. 最初，S1 和 S2 區域都是空的，即除了指定的樞軸點 p 之外的所有項目都在未知區域中。
   2. 然後，對于未知區域中的每個項目 a [k]，我們将 a[k] 與 p 進行比較, 并決定兩種情況中的一個：
      1. 如果 a [k]≥p，則将 a[k] 放入 S2 或
      2. 否則，将 a[k] 放入 S1 中。
   3. 接下來的兩張幻燈片将會詳細闡述了這兩種情況。
   4. 最後，我們交換a[i]和 a[m] 來将樞紐 p 放在 S1 和 S2 的中間。
5. 分區排序 - 當a[k] >= p的情況：

   1. 

6. 分區排序 - 當a[k] < p的情況：

   1. 

7. 分區排序 - c++實作：
   • int partition(int a[], int i, int j) {
     • int p = a[i]; // p 是樞紐
     • int m = i; // S1 和 S2 一開始是空的
     • for (int k = i+1; k <= j; k++) { // 探索未知的區域
       • if (a[k] < p) { // case 2
         • m++;
         • swap(a[k], a[m]); // C++ STL algorithm std::swap
       • } // 注意：在情況1的時候我們什麼不做: a[k] >= p
     • }
     • swap(a[i], a[m]); // 最後一步, 用a[m]交換樞紐
     • return m; // 傳回樞紐的指數, 用于快速排序（Quick Sort）
   • }
8. 快速排序c++實作：
   • void quickSort(int a[], int low, int high) {
     • if (low < high) {
       • int m = partition(a, low, high); // O(N)
       • // a[low..high] ~> a[low..m–1], pivot, a[m+1..high]
       • quickSort(a, low, m-1); // 遞歸地将左子陣列排序
       • // a[m] = pivot 在分區後就被排序好了
       • quickSort(a, m+1, high); // 然後将右子陣列排序
     • }
   • }
9. 快速排序：第一部分 分析：
   1. 首先，我們分析跑一次分區的成本。
   2. 在内部分區（a，i，j）中，隻有一個for循環周遊（j-i）次。 由于j可以和 N-1一樣大，i 可以低至0，是以分區的時間複雜度是O（N）。
   3. 類似于歸并排序分析，快速排序的時間複雜度取決于分區（a，i，j）被調用的次數。
10. 快速排序：第三部分 分析：（第二部分，略）
    1. 在這種最壞情況的輸入場景（最壞場景指的是已排序序列）中，會發生以下情況：

    2. 

    3. 第一個分區需要O（N）時間，将a分成0,1，N-1個項目，然後向右遞歸。
    4. 第二個花費O（N-1）時間，将a分成0,1，N-2個項目，然後再次向右遞歸...
    5. 直到最後，第N個分區将a分成0,1,1項，并且Quick Sort遞歸停止。
    6. 這是經典的N +（N-1）+（N-2）+ ... + 1模式，它是O（N2），類似于本幻燈片中的分析......
11. 快速排序：最好的情況（極少）：
    1. 當分區總是将數組分成兩個相等的一半時，就會發生快速排序的最佳情況，如歸并排序。
    2. 當發生這種情況時，遞歸的深度隻有O（log N）。
    3. 由于每個級别進行O（N）比較，時間複雜度為O（N log N）。
12. 代碼：

int partition(int arr[], int low, int high)
{
    int mid_data = 0, tmp_data = 0;
    int mid_index = 0, index = 0;
    
    mid_data  = arr[low];
    mid_index = low;
    
    printf("---------- call partition----------\n");                                                                                              

    for (index = low + 1; index <= high; index++) { 
        if (arr[index] < mid_data) {   
            mid_index++;                   

            printf("[index:%2d<-->%2d], data: %2d<-->%2d\n",
                            mid_index, index, arr[mid_index], arr[index]);
            tmp_data = arr[index];
            arr[index] = arr[mid_index];
            arr[mid_index] = tmp_data;
        }
    }

    printf("[index:%2d<-->%2d], data: %2d<-->%2d\n",
                    low, mid_index, arr[low], arr[mid_index]);

    tmp_data = arr[mid_index];
    arr[mid_index] = arr[low];
    arr[low] = tmp_data;

    return mid_index;
}

void QuickSort(int arr[], int low, int high)
{
    if (low < high) {
        int mid = partition(arr, low, high);
        QuickSort(arr, low, mid-1);
        QuickSort(arr, mid+1, high);
    }

    return;
}