C++ 中的氣泡排序演算法

Jinku Hu 2023年1月30日 2021年6月28日
  1. std::vector 容器實現氣泡排序
  2. 使用經驗計時測量分析氣泡排序的複雜性
C++ 中的氣泡排序演算法

本文將講解如何在 C++ 中實現氣泡排序演算法的幾種方法。

std::vector 容器實現氣泡排序

氣泡排序是最簡單的排序演算法之一。它遍歷比較每個相鄰對的物件列表,如果它們沒有排序,則交換元素。它被歸類為比較排序演算法,因為元素的唯一讀取是使用比較表示式完成的。在下面的示例程式碼中,我們實現了氣泡排序來處理通用的 vector 物件。一個名為 bubbleSort 的函式就足以定義整個排序程式。該函式是模板化的,並將對 vector 的引用作為唯一引數。

bubbleSort 包括兩個巢狀的 for 迴圈來迭代 vector 元素,直到它們按升序排序。請注意,外部 for 迴圈的每次迭代都會在正確的位置儲存一個元素。後一個元素儲存在向量的末尾,它恰好是在內迴圈中遍歷的向量部分中最大的元素。請注意,我們使用了 std::swap 演算法來簡化實現並使其更具可讀性。

#include <iostream>
#include <vector>
#include <algorithm>

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 <iostream>
#include <vector>
#include <algorithm>
#include <sys/time.h>
#include <ctime>

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
Author: Jinku Hu
Jinku Hu avatar Jinku Hu avatar

Founder of DelftStack.com. Jinku has worked in the robotics and automotive industries for over 8 years. He sharpened his coding skills when he needed to do the automatic testing, data collection from remote servers and report creation from the endurance test. He is from an electrical/electronics engineering background but has expanded his interest to embedded electronics, embedded programming and front-/back-end programming.

LinkedIn

相關文章 - C++ Algorithm