数据结构-排序（四）冒泡排序

1、算法思想

基于“交换”的排序： 根据序列中两个元素关键字的比较结果来对换这两个记录在序列中的位置

冒泡排序的算法思想是： 每次比较两个相邻的元素，若为逆序（即A[i-1]>A[i]）顺序错误，就把他们交换过来。从第一个元素起。比较相邻的元素，如果第一个比第一个大，就交换。然后继续比较，直到最大的数到最后一个。称这样过程为“⼀趟”冒泡排序。所有元素重复以上动作。直到序列比较完。

举个例子，需要对数组a[5,8,3,4,2]进行从小到大排序

从小到大排序就需要将最大的数冒到最后面

int a[] = {5,8,3,4,2};
for (int i = 0; i < a.length - 1; i++){ // 5个数排序，只用进行n-1趟，即4趟
for (int j = 0; j < a.length - 1 - i; j++){
//从第1位开始比较直到最后一个归位的数，i可以认为为已经归位了几个数字
//第一趟 i = 0
第一次: 5 8 3 4 2   (j = 0) //5和8比较
第二次: 5 3 8 4 2   (j = 1) //8和3比较
第三次: 5 3 4 8 2   (j = 2) //8和4比较
第四次: 5 3 4 2 [8] (j = 3) //8和2比较，8归位

//第二趟 i = 1
第一次: 3 5 4 2 [8] (j = 0) //5和3比较
第二次: 3 4 5 2 [8] (j = 1) //5和4比较
第三次: 3 4 2 5 [8] (j = 2) //5和2比较，5归位

//第三趟 i = 2
第一次: 3 4 2 [5 8] (j = 0) //3和4比较
第二次: 3 2 [4 5 8] (j = 1) //4和2比较，4归位

//第四趟 i = 3
第一次: 2 [3 4 5 8] (j = 0) //3和2比较，2,3归位

以上gif动图制作，图像来自网站：VisuAlgo

2、代码实现

#include <iostream>
#include <string>
using namespace std;

/**
 * 冒泡排序
 * @param arr
 * @param n
 */
void BubbleSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        bool flag = false;
        for (int j = 0; j < n - i - 1; j++) { //一趟冒泡排序
            if (arr[j] > arr[j + 1]) { //升序排列
                //arr[j] > arr[j + 1] 降序排列
                swap(arr[j], arr[j + 1]); //交换顺序数值函数
                flag = true;
            }//if
        }//for
        if (!flag) { //本趟遍历后没有交换顺序，说明已经有序
            return;
        }
    }//for
}
/**
 * 输出数组
 * @param arr
 * @param n
 */
void PrintArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        cout << arr[i] << "  ";
    }
    printf("\n");
}
int main() {
    int arr[] = {12, 28, 20, 50, 48, 1, 5, 28};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "输出arr初始数组" << endl;
    PrintArray(arr, n);
    cout << "arr冒泡排序" << endl;
    BubbleSort(arr, n);
    cout << "输出arr排序后数组" << endl;
    PrintArray(arr, n);
    return 0;
}

输出arr初始数组
12  28  20  50  48  1  5  28
arr冒泡排序
输出arr排序后数组
1  5  12  20  28  28  48  50

3、算法效率分析

1、空间复杂度： $O(1)$

2、时间复杂度

最好情况（有序）： $比较次数 = n - 1；交换次数 = 0；最好时间复杂度 = O(n)$

最坏情况（逆序）：

$比较次数 = (n - 1) + (n - 2 )+…+ 1 = \frac{n(n-1)}{2} = 交换次数；最坏时间复杂度 = O(n^2)$

平均时间复杂度: $O(n^2)$

3、稳定性： 稳定