用 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
