快速排序及優化

快速排序

每次從當前考慮的數組中選一個元素，把這個元素想辦法挪到應該排好序的位置，比如4這個元素，它就有一個性質4之前的元素都是小於它的，之後的元素都是大於它的，之後我們要做的事情是對小於4和大於4的數組分別繼續使用快速排序的思路，逐漸遞歸下去完成整個排序過程。

對於快速排序如果把選定的元素挪到正確的位置的過程也是快速排序的核心，在這個過程中我們通常選擇數組第一個元素為我們分界的標誌點，我們記錄這個點為 l ，之後我們逐漸的遍歷右邊所有沒有被訪問的元素，在遍歷的過程中我們逐漸整理一部分是小於v這個元素的，一部分是大於v這個元素的，當讓我們要有個記錄那個是小於v和大於v的分界點，這個點為 j ，而當前訪問的元素記錄為 i。

我們如何來決定當前的元素要怎樣變化才能維持當前的性質，如果當前的元素e是比v還要大的，那麼他直接就放在大於v一部分的後面。

然後就考慮下一元素就好了。

如果當前的元素e是比v還要小的。

我們只需要當前橙色部分也就是j所指的位置的後一個元素和當前做考察的元素 i進行一下交換。

之後我們進行一下位置維護 ++j，++i。

以此類推，整個數組分成三個部分，第一個元素是v，橙色部分小於v，紫色部分大於v。

最後我們需要做的是把數組 l這個位置和數組j這個位置進行交換，這樣整個數組就形成了我們設想的那樣，前面小於v，後面大於v。

優化

對於小規模數組, 使用插入排序進行優化；
隨機在arr[l…r]的範圍中, 選擇一個數值作為標定點pivot。在快速排序遞歸過程中分成的子樹不能保證每次都是平均的將整個數組一分為二，換句話來說分成的子數組可能是一大一小的。
如果數組近乎或完全有序那麼：

quickSort

// 對arr[l...r]範圍的數組進行插入排序
template<typename T>
void insertionSort(T arr[], int l, int r) {
   for (int i = l + 1; i <= r; ++i) {
       T e = arr[i];
       int j;
       for (j = i; j > l && arr[j - 1] > e; --j) {
           arr[j] = arr[j - 1];
       }
       arr[j] = e;
   }
}

// 對arr[l...r]部分進行partition操作
// 返回p, 使得arr[l...p-1] < arr[p] ; arr[p+1...r] > arr[p]
template<typename T>
int __partition1(T arr[], const int l, const int r) {
   // 優化：隨機在arr[l...r]的範圍中, 選擇一個數值作為標定點pivot
   std::swap(arr[l], arr[rand() % (r - l + 1) + l]);
   const T v = arr[l];
   int j = l;
   // arr[l+1...j] < v ; arr[j+1...i) > v
   for (int i = l + 1; i <= r; ++i) {
       if (arr[i] < v) {
           std::swap(arr[++j], arr[i]);
       }
   }
   std::swap(arr[l], arr[j]);
   return j;
}
// 對arr[l...r]部分進行快速排序
template<typename T>
void __quickSort(T arr[], const int l, const int r) {
   // 優化：對於小規模數組, 使用插入排序進行優化
   if (r - l <= 15) {
       insertionSort(arr, l, r);
       return;
   }
   const int p = __partition1(arr, l, r);
   __quickSort(arr, l, p - 1);
   __quickSort(arr, p + 1, r);
}

//快速排序
template<typename T>
void quickSort(T arr[], const int n) {
   srand(time(NULL));
   __quickSort(arr, 0, n - 1);
}

雙路快速排序

在之前的快速排序我們沒有討論在等於v的情況，在這裡無論是把等於放在左邊還是右邊，如果整個數組出現大量重複的元素，那麼它就會造成左右分成的數組極度不平衡從而使演算法退化成O(n^2)。

現在呢我們將小於v和大於v放在數組的兩端。首先我們從i這個位置開始向後掃描，當我們面對的元素仍然是小於v的時候我們繼續向後掃描，知道我們碰到了元素e，它是大於等於v的。

同樣 j 亦是如此，

這樣話兩個綠色的部分就分別歸併到橙色和紫色。

而 i和 j這兩個所指的元素交換一下位置就可以了。

然後維護一下位置 ++i，–j，以此類推。

quickSort2Ways

// 對arr[l...r]範圍的數組進行插入排序
template<typename T>
void insertionSort(T arr[], int l, int r) {
   for (int i = l + 1; i <= r; ++i) {
       T e = arr[i];
       int j;
       for (j = i; j > l && arr[j - 1] > e; --j) {
           arr[j] = arr[j - 1];
       }
       arr[j] = e;
   }
}

// 雙路快速排序的partition
// 返回p, 使得arr[l...p-1] <= arr[p] ; arr[p+1...r] >= arr[p]
// 雙路快排處理的元素正好等於arr[p]的時候要注意，詳見下面的注釋：）
template<typename T>
int __partition2(T arr[], int l, int r) {
   // 隨機在arr[l...r]的範圍中, 選擇一個數值作為標定點pivot
   std::swap(arr[l], arr[rand() % (r - l + 1) + l]);
   const T v = arr[l];
   // arr[l+1...i) <= v; arr(j...r] >= v
   int i = l + 1, j = r;
   while (true) {
       // 注意這裡的邊界, arr[i] < v, 不能是arr[i] <= v
       // 思考一下為什麼?
       while (i <= r && arr[i] < v)++i;
       // 注意這裡的邊界, arr[j] > v, 不能是arr[j] >= v
       // 思考一下為什麼?
       while (j >= l + 1 && arr[j] > v)--j;
       if (i > j)break;
       std::swap(arr[i], arr[j]);
       //arr[i] < v. 在碰到很多連續相同數字的情況下，i只向後移動一次，同時j至少向前移動一次，相對平衡。
       //arr[i] <= vb, 在碰到很多連續相同數字的情況下, i首先不停向後移動，直到滿足條件為止，造成不平衡。
       ++i;
       --j;
   }
   std::swap(arr[l], arr[j]);
   return j;
}

// 對arr[l...r]部分進行快速排序
template<typename T>
void __quickSort2Ways(T arr[], const int l, const int r) {
   // 對於小規模數組, 使用插入排序進行優化
   if (r - l <= 15) {
       insertionSort(arr, l, r);
       return;
   }
   const int p = __partition2(arr, l, r);
   __quickSort2Ways(arr, l, p - 1);
   __quickSort2Ways(arr, p + 1, r);
}

//快速排序
template<typename T>
void quickSort2Ways(T arr[], const int n) {
   srand(time(NULL));
   __quickSort2Ways(arr, 0, n - 1);
}

三路快速排序

之前快速排序的思想都是小於v大於v，而三路快速排序的思想是小於v等於v大於v。在這樣分割之後在遞歸的過程中，對於等於v的我們根本不用管了，只需要遞歸小於v大於v的部分進行同樣的快速排序。

現在我們要處理i位置這個元素e，如果當前元素 e 正好等於v，那麼元素e就直接納入綠色的等於v的部分，相應的 ++i，我們來處理下一位置的元素。

如果當前元素 e 小於v，我們只需要把這個元素和等於v部分的第一個元素進行一次交換就好了。

之後因該維護一下位置，++i，++lt，來查看下一元素。

如果當前元素 e 大於v，我們只需要把這個元素和gt-1位置的元素進行一次交換就好了。

相應的我們應該維護一下gt的位置 –gt，需要注意的是i我們不需要動它，因為和它交換的位置元素本就沒有討論過。

以此類推，最後還需要l和lt位置的元素交換一下位置。

此時我們整個數組就變成了這個樣子，之後我們只需要對小於v的部分和大於v的部分進行遞歸的快速排序就好了，至於等於v的部分它已經放在數組合適的位置了。

quickSort3Ways

// 對arr[l...r]範圍的數組進行插入排序
template<typename T>
void insertionSort(T arr[], int l, int r) {
   for (int i = l + 1; i <= r; ++i) {
       T e = arr[i];
       int j;
       for (j = i; j > l && arr[j - 1] > e; --j) {
           arr[j] = arr[j - 1];
       }
       arr[j] = e;
   }
}

// 遞歸的三路快速排序演算法
template<typename T>
void __quickSort3Ways(T arr[], const int l, const int r) {
   // 對於小規模數組, 使用插入排序進行優化
   if (r - l <= 15) {
       insertionSort(arr, l, r);
       return;
   }

   // 隨機在arr[l...r]的範圍中, 選擇一個數值作為標定點pivot
   std::swap(arr[l], arr[rand() % (r - l + 1) + l]);

   T v = arr[l];

   int lt = l;     // arr[l+1...lt] < v
   int gt = r + 1; // arr[gt...r] > v
   int i = l + 1;    // arr[lt+1...i) == v
   while (i < gt) {
       if (arr[i] < v) {
           std::swap(arr[i], arr[lt + 1]);
           ++i;
           ++lt;
       } else if (arr[i] > v) {
           std::swap(arr[i], arr[gt - 1]);
           --gt;
       } else { // arr[i] == v
           ++i;
       }
   }
   std::swap(arr[l], arr[lt]);
   __quickSort3Ways(arr, l, lt - 1);
   __quickSort3Ways(arr, gt, r);
}

// 對於包含有大量重複數據的數組, 三路快排有巨大的優勢
template<typename T>
void quickSort3Ways(T arr[], const int n) {
   srand(time(nullptr));
   __quickSort3Ways(arr, 0, n - 1);
}

概述

Tags: 快速排序排序演算法演算法演算法與數據結構