用 C++ 實現歸併排序演算法
本文將介紹如何用 C++ 實現一個歸併排序演算法。
在 C++ 中為 std::vector 容器實現合併排序
歸併排序利用分治策略來達到效率，可以作為大列表的通用排序演算法。該演算法背後的思想是將輸入向量劃分為多個較小的向量，然後對每個向量進行排序。完成較小的向量後，我們可以將它們合併到一個列表中，這恰好是一個相對更直接的操作。請注意，以下程式碼示例使用遞迴實現此方法，因為它最適合此解決方案。使用遞迴過程將原始向量多次劃分，直到我們得到二元素向量，此時將呼叫比較函式。當每一對被排序後，它們被合併成四元素向量，依此類推，直到遞迴的最後一級返回。
mergeSort 函式是遞迴過程的核心部分。它將向量引用作為唯一引數並檢查大小是否小於等於 1。如果是，則該向量符合排序條件，並且函式返回。當向量包含兩個或更多元素時，它會被拆分為兩個單獨的向量物件，並對每個物件呼叫 mergeSort 函式。請注意，後一部分強制從最小的子向量開始排序。一旦遞迴達到這樣的水平，兩個 mergeSort 函式都會返回，並且下面的程式碼開始執行。首先，清除 vec 向量，然後呼叫 merge 函式。merge 功能是通過一個迭代過程實現的，可以通過仔細觀察來理解。通常，後一步將最小的排序向量連線到一個向量物件中。
#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>
void merge(vector<T> &vec, vector<T> &v1, vector<T> &v2) {
auto siz1 = v1.size();
auto siz2 = v2.size();
size_t p1 = 0;
size_t p2 = 0;
while (p1 < siz1 && p2 < siz2) {
if (v1.at(p1) < v2.at(p2))
vec.push_back(v1.at(p1++));
else
vec.push_back(v2.at(p2++));
}
while (p1 < siz1) vec.push_back(v1.at(p1++));
while (p2 < siz2) vec.push_back(v2.at(p2++));
}
template <typename T>
void mergeSort(vector<T> &vec) {
if (vec.size() <= 1) return;
auto iter = vec.begin() + vec.size() / 2;
vector<T> v1(vec.begin(), iter);
vector<T> v2(iter, vec.end());
mergeSort(v1);
mergeSort(v2);
vec.clear();
merge(vec, v1, v2);
}
int main() {
vector<int> vec1 = {43, 5, 123, 94, 359, -23, 2, -1};
printVector(vec1);
mergeSort(vec1);
printVector(vec1);
return EXIT_SUCCESS;
}
輸出：
43; 5; 123; 94; 359; -23; 2; -1;
-23; -1; 2; 5; 43; 94; 123; 359;
或者，可以使用 STL std::merge 演算法重寫先前的程式碼，該演算法可以簡化程式碼以供閱讀。請注意，std::merge 函式替代了我們的 merge 實現，並且向量合並可以通過 mergeSort 函式體中的單個語句完成。當最後一級遞迴在第一次呼叫 mergeSort 時返回兩個向量時，最後一次呼叫 std::merge 會將排序後的內容儲存在原始 vec 物件中，可以從 main 函式觀察到。
#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>
void mergeSort2(vector<T> &vec) {
if (vec.size() <= 1) return;
auto iter = vec.begin() + vec.size() / 2;
vector<T> v1(vec.begin(), iter);
vector<T> v2(iter, vec.end());
mergeSort2(v1);
mergeSort2(v2);
vec.clear();
std::merge(v1.begin(), v1.end(), v2.begin(), v2.end(),
std::back_inserter(vec));
}
int main() {
vector<int> vec1 = {43, 5, 123, 94, 359, -23, 2, -1};
printVector(vec1);
mergeSort2(vec1);
printVector(vec1);
return EXIT_SUCCESS;
}
使用經驗時序測量分析歸併排序的複雜性
合併排序提供 O(nlogn) 最壞情況執行時間，這恰好是當代通用排序演算法中最好的之一。它在最壞情況下的線性空間複雜度超過了快速排序演算法。當實現使用有效的方法來選擇樞軸變數時，後者在實踐中往往相對更快。
儘管遞迴方法可能很難理解，但你始終可以使用偵錯程式深入瞭解每一步的細節。但是，在更高階別上，我們可以使用以下程式碼示例來計算不同向量大小之間的遞迴函式呼叫。請注意，遞迴呼叫的總和往往是函式 - 2n - 2，其中 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>
void mergeSort2(vector<T> &vec, int &level) {
if (vec.size() <= 1) return;
auto iter = vec.begin() + vec.size() / 2;
vector<T> v1(vec.begin(), iter);
vector<T> v2(iter, vec.end());
mergeSort2(v1, ++level);
mergeSort2(v2, ++level);
vec.clear();
std::merge(v1.begin(), v1.end(), v2.begin(), v2.end(),
std::back_inserter(vec));
}
int main() {
vector<int> vec3(100, 10);
vector<int> vec4(200, 10);
int recursion_level = 0;
mergeSort2(vec3, recursion_level);
cout << "recursion level: " << recursion_level << endl;
recursion_level = 0;
mergeSort2(vec4, recursion_level);
cout << "recursion level: " << recursion_level << endl;
return EXIT_SUCCESS;
}
輸出：
recursion level: 198
recursion level: 398
