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