用 C++ 實現快速排序演算法
本文將演示如何在 C++ 中實現快速排序演算法的多種方法。
為 std::vector 容器實現快速排序
快速排序是當代程式碼庫中使用的最快的通用排序演算法之一。它利用了類似於歸併排序演算法的分而治之的技術。雖然，前者依賴於通常稱為分割槽的操作。原始向量在稱為 pivot 的元素上分割，它在它之前分隔較小的元素，在它之後分隔較大的元素。請注意，這些比較與使用者應選擇的樞軸值相關。選擇主元值恰好是該演算法效能的關鍵因素，我們將在本文後面進行分析。此時，讓我們假設樞軸元素是原始向量中的第一個元素。一旦我們有了樞軸選擇的方法，我們就可以將向量分割成兩個較小的向量，這些向量將在原地遞迴排序。請注意，快速排序操作類似於歸併排序，因為它也會多次分割向量，直到它們的起始位置相互交叉。
以下示例程式碼使用遞迴 sort 函式實現演算法，該函式在每次呼叫時呼叫 partitionVec 函式。通過交換同一向量物件中的元素，可以線上性時間內完成分割槽過程。後面的操作是使用 partitionVec 函式來實現的，它也以某種方式充當排序函式。
#include <algorithm>
#include <iostream>
#include <vector>
using std::cout;
using std::endl;
using std::string;
using std::vector;
template <typename T>
void printVector(const vector<T> &vec) {
for (auto &i : vec) {
cout << i << "; ";
}
cout << endl;
}
template <typename T>
T partitionVec(vector<T> &vec, size_t start, size_t end) {
T pivot = vec.at(start);
auto lh = start + 1;
auto rh = end;
while (true) {
while (lh < rh && vec.at(rh) >= pivot) rh--;
while (lh < rh && vec.at(lh) < pivot) lh++;
if (lh == rh) break;
T tmp = vec.at(lh);
vec.at(lh) = vec.at(rh);
vec.at(rh) = tmp;
}
if (vec.at(lh) >= pivot) return start;
vec.at(start) = vec.at(lh);
vec.at(lh) = pivot;
return lh;
}
template <typename T>
void sort(vector<T> &vec, size_t start, size_t end) {
if (start >= end) return;
auto boundary = partitionVec(vec, start, end);
sort(vec, start, boundary);
sort(vec, boundary + 1, end);
}
template <typename T>
void quickSort(vector<T> &vec) {
sort(vec, 0, vec.size() - 1);
}
int main() {
vector<int> vec1 = {43, 5, 123, 94, 359, -23, 2, -1};
printVector(vec1);
quickSort(vec1);
printVector(vec1);
return EXIT_SUCCESS;
}
輸出：
43; 5; 123; 94; 359; -23; 2; -1;
-23; -1; 2; 5; 43; 94; 123; 359;
調查 Quicksort 實現中的遞迴級別
快速排序的平均時間複雜度為 O(nlogn)，與歸併排序演算法相當。但是請注意，快速排序演算法高度依賴於樞軸選擇方法。在這種情況下，我們選擇了天真的版本來選擇樞軸值，它是向量中的第一個元素。在某些情況下，這可能會產生 O(n2) 的非常糟糕的執行時間。在實踐中，選擇隨機主元很有可能產生 O(nlogn) 效能。但是，如果需要最大效能，則應該瞭解基於輸入資料的樞軸選擇方法。
我們可以使用額外的函式引數觀察前面程式碼片段中的遞迴過程，該引數對 sort 函式的每次呼叫進行計數。下面的示例對兩個不同大小的向量執行類似的測試並列印相應的總和。請注意，遞迴呼叫的總和將向量大小與以下函式 - 2n - 1 相關聯，其中 n 表示元素的數量。
#include <algorithm>
#include <iostream>
#include <vector>
using std::cout;
using std::endl;
using std::string;
using std::vector;
template <typename T>
void printVector(const vector<T> &vec) {
for (auto &i : vec) {
cout << i << "; ";
}
cout << endl;
}
template <typename T>
auto partitionVec(vector<T> &vec, size_t start, size_t end) {
T pivot = vec.at(start);
auto lh = start + 1;
auto rh = end;
while (true) {
while (lh < rh && vec.at(rh) >= pivot) rh--;
while (lh < rh && vec.at(lh) < pivot) lh++;
if (lh == rh) break;
T tmp = vec.at(lh);
vec.at(lh) = vec.at(rh);
vec.at(rh) = tmp;
}
if (vec.at(lh) >= pivot) return start;
vec.at(start) = vec.at(lh);
vec.at(lh) = pivot;
return lh;
}
template <typename T>
void sort(vector<T> &vec, size_t start, size_t end, int &level) {
if (start >= end) return;
auto boundary = partitionVec(vec, start, end);
sort(vec, start, boundary, ++level);
sort(vec, boundary + 1, end, ++level);
}
template <typename T>
void quickSort(vector<T> &vec, int &level) {
sort(vec, 0, vec.size() - 1, ++level);
}
int main() {
vector<int> vec3(100, 10);
vector<int> vec4(200, 10);
int recursion_level = 0;
quickSort(vec3, recursion_level);
cout << "level: " << recursion_level << endl;
recursion_level = 0;
quickSort(vec4, recursion_level);
cout << "level: " << recursion_level << endl;
return EXIT_SUCCESS;
}
輸出：
level: 199
level: 399
