用 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
