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
