冒泡排序

冒泡排序（Bubble Sort）是最基础的交换排序算法，其核心思想是：相邻两个元素两两比较，如果逆序则交换，经过 n-1 趟排序后整个序列有序。

"冒泡"的含义：每一趟排序都会将关键字最小（或最大）的元素像气泡一样"浮"到序列的一端。

关键特性

1. 相邻元素两两比较（区别于选择排序）
2. 每一趟排序能保证一个元素到达最终位置（区别于插入排序）
3. 冒泡排序产生的有序子序列是全局有序的
4. 稳定的排序算法
5. 可以用于链表排序

基本冒泡排序

1. 从序列的最后一个元素开始，依次比较相邻的两个元素
2. 如果 A[j-1] > A[j]（逆序），则交换这两个元素
3. 从后往前比较，直到比较到序列开头，一趟冒泡排序完成
4. 一趟排序后，最小的元素到达序列的最前面
5. 重复步骤 1–4，共执行 n-1 趟

优化版本

优化一：提前终止——设置标志位 flag，若某趟没有交换说明已有序，提前结束。

优化二：记录最后交换位置——记录每趟最后一次交换位置 last，下一趟只需比较到 last。

基本冒泡排序

void BubbleSort(int A[], int n) {
    int i, j, temp;
    for (i = 0; i < n - 1; i++) {  // 共 n-1 趟
        for (j = n - 1; j > i; j--) {  // 从后往前
            if (A[j-1] > A[j]) {  // 逆序则交换
                temp = A[j-1];
                A[j-1] = A[j];
                A[j] = temp;
            }
        }
    }
}

优化版本一：提前终止

void BubbleSort_Opt1(int A[], int n) {
    int i, j, temp;
    int flag;  // 标志位
    for (i = 0; i < n - 1; i++) {
        flag = 0;  // 每趟开始时置 0
        for (j = n - 1; j > i; j--) {
            if (A[j-1] > A[j]) {
                temp = A[j-1];
                A[j-1] = A[j];
                A[j] = temp;
                flag = 1;  // 发生交换，置 1
            }
        }
        if (flag == 0)  // 没有交换，已经有序
            return;
    }
}

优化版本二：记录最后交换位置

void BubbleSort_Opt2(int A[], int n) {
    int j, temp;
    int last = n - 1;  // 最后交换的位置
    while (last > 0) {
        int newLast = 0;
        for (j = n - 1; j > last - 1; j--) {
            if (A[j-1] > A[j]) {
                temp = A[j-1];
                A[j-1] = A[j];
                A[j] = temp;
                newLast = j;  // 更新最后交换位置
            }
        }
        last = newLast;  // 下一趟只需比较到 newLast
    }
}

对序列 {49, 38, 65, 97, 76, 13, 27, 49*} 进行冒泡排序（从小到大）：

初始:    49  38  65  97  76  13  27  49*

第1趟:   从后往前两两比较交换
         49  38  65  97  76  13  27  49*   ← 比较 27<49*，不交换
                              ↑比较 13<27，不交换
                      ↑比较 76>13，交换 → 49  38  65  97  13  76  27  49*
              ↑比较 97>13，交换 → 49  38  65  13  97  76  27  49*
          ↑比较 65>13，交换 → 49  38  13  65  97  76  27  49*
      ↑比较 38>13，交换 → 49  13  38  65  97  76  27  49*
  ↑比较 49>13，交换 → [13] 49  38  65  97  76  27  49*
         最小值 13 到达最终位置 ✓

第2趟:   → [13  27] 49  38  65  97  76  49*
第3趟:   → [13  27  38] 49  65  97  76  49*
第4趟:   → [13  27  38  49] 65  97  76  49*
第5趟:   → [13  27  38  49  49*] 65  97  76   （49 == 49* 不交换，保持稳定性）
第6趟:   → [13  27  38  49  49*  65] 76  97
第7趟:   → [13  27  38  49  49*  65  76  97]

最终结果：13, 27, 38, 49, 49*, 65, 76, 97（稳定！）

空间复杂度为 $O(1)$：只需要一个临时变量用于交换，是原地排序算法。