快速排序及優化

快速排序

每次從當前考慮的陣列中選一個元素，把這個元素想辦法挪到應該排好序的位置，比如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);
}

概述

標籤：其他

上一篇：網路流，二分圖與圖的匹配

下一篇：【Unity基礎知識】認識常用的生命周期函式（Awake、Start、Update...）