C++ 中的冒泡排序算法
Jinku Hu
2023年10月12日
本文将讲解如何在 C++ 中实现冒泡排序算法的几种方法。
为 std::vector 容器实现冒泡排序
冒泡排序是最简单的排序算法之一。它遍历比较每个相邻对的对象列表，如果它们没有排序，则交换元素。它被归类为比较排序算法，因为元素的唯一读取是使用比较表达式完成的。在下面的示例代码中，我们实现了冒泡排序来处理通用的 vector 对象。一个名为 bubbleSort 的函数就足以定义整个排序程序。该函数是模板化的，并将对 vector 的引用作为唯一参数。
bubbleSort 包括两个嵌套的 for 循环来迭代 vector 元素，直到它们按升序排序。请注意，外部 for 循环的每次迭代都会在正确的位置存储一个元素。后一个元素存储在向量的末尾，它恰好是在内循环中遍历的向量部分中最大的元素。请注意，我们使用了 std::swap 算法来简化实现并使其更具可读性。
#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 bubbleSort(vector<T> &vec) {
for (size_t i = 0; i < vec.size() - 1; ++i) {
for (size_t j = 0; j < vec.size() - i - 1; ++j) {
if (vec.at(j) > vec.at(j + 1)) std::swap(vec.at(j), vec.at(j + 1));
}
}
}
int main() {
vector<int> vec1 = {43, 5, 123, 94, 359, -23, 2, -1};
printVector(vec1);
bubbleSort(vec1);
printVector(vec1);
return EXIT_SUCCESS;
}
输出：
43; 5; 123; 94; 359; -23; 2; -1;
-23; -1; 2; 5; 43; 94; 123; 359;
使用经验计时测量分析冒泡排序的复杂性
冒泡排序属于二次运行时类。事实上，这个算法的平均时间和最坏情况的性能都是二次的 - O(n2)。因此，对于大型输入数据集，这种方法变得非常低效。正是因为这个原因，它实际上并没有被使用。例如，如果我们将输入向量长度增加 10，运行时间将大致增加 100 倍。但是请注意，当输入向量中的元素仅在一个地方乱序（例如，1032547698 序列）时，冒泡排序对于特殊情况可能非常有效。后一种情况会使算法复杂度呈线性。以下代码示例使用 gettimeofday 函数测量两个不同向量的运行时间，并将结果输出到控制台。
#include <sys/time.h>
#include <algorithm>
#include <ctime>
#include <iostream>
#include <vector>
using std::cout;
using std::endl;
using std::string;
using std::vector;
template <typename T>
void bubbleSort(vector<T> &vec) {
for (size_t i = 0; i < vec.size() - 1; ++i) {
for (size_t j = 0; j < vec.size() - i - 1; ++j) {
if (vec.at(j) > vec.at(j + 1)) std::swap(vec.at(j), vec.at(j + 1));
}
}
}
float time_diff(struct timeval *start, struct timeval *end) {
return (end->tv_sec - start->tv_sec) + 1e-6 * (end->tv_usec - start->tv_usec);
}
int main() {
struct timeval start {};
struct timeval end {};
vector<int> vec3(100, 10);
vector<int> vec4(1000, 10);
gettimeofday(&start, nullptr);
bubbleSort(vec3);
gettimeofday(&end, nullptr);
printf("bubbleSort %zu elements: %0.8f sec\n", vec3.size(),
time_diff(&start, &end));
gettimeofday(&start, nullptr);
bubbleSort(vec4);
gettimeofday(&end, nullptr);
printf("bubbleSort %zu elements: %0.8f sec\n", vec4.size(),
time_diff(&start, &end));
return EXIT_SUCCESS;
}
输出：
bubbleSort 100 elements: 0.00002500 sec
bubbleSort 1000 elements: 0.00184900 sec
作者： Jinku Hu
