冒泡排序

〇、返回

一、概述

冒泡排序（Bubble Sort）是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。

二、工作原理及算法步骤

1. 比较相邻的元素。如果第一个比第二个大，就交换它们两个。

2. 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。

3. 针对所有的元素重复以上的步骤，除了最后一个。

4. 持续每次对越来越少的元素重复上面的直到没有任何一对数字需要比较。

三、代码实现（C++）

#include<bits/stdc++.h>

using namespace std;

int main() {

    int n;

    cin>>n;

    vector<int> a(n);

    for (int i=0;i<n;i++) {        // 读入数组

        cin>>a[i];

    }

    for (int i=1;i<=n;i++) {        // 操作次数

        bool flag=true;        // 数组是否已经排好序

        for (int j=0;j<n-i;j++) {        // 步骤1、2

            if (a[j]>a[j+1]) {

                swap(a[j],a[j+1]);

                flag=false;

            }

        }

        if (flag==true) {        // 如果已经排好序就退出循环

            break;

        }

    }

    for (int i=0;i<n;i++) {        // 输出数组

        cout<<a[i]<<" ";

    }

    cout<<"\n";

    return 0;

}

四、时空复杂度及稳定性

时间复杂度

最坏情况时间复杂度：O($n^2$)（当输入数组是反向排序的时候）

最好情况时间复杂度：O(n)（当输入数组已经是排序好的时候）

平均情况时间复杂度：O($n^2$)

空间复杂度

冒泡排序的空间复杂度为 O(1)，因为它只需要一个额外的临时变量来进行交换操作。

稳定性

冒泡排序是一种稳定的排序算法，即相等的元素在排序前后相对位置不变。

五、总结

冒泡排序虽然简单，但在大多数情况下并不是最优的排序算法，特别是在数据量较大的情况下。然而，它对于理解排序算法的基本概念和原理非常有帮助。在实际应用中，更高效的排序算法如快速排序、归并排序等更为常用。