冒泡排序

#冒泡排序

• 什么是冒泡排序
• 操作步骤
• 时间复杂度
• 特点

#什么是冒泡排序

冒泡排序重复「从序列右边开始比较相邻两个数字的大小，根据结果交换位置」。数字会像泡泡一样，慢慢从右往左「浮」到序列顶端——这就是「冒泡」名字的由来。

  5  9  3  1  2  8  4  7  6
              ↑
    最小的数字 1 会像泡泡一样慢慢浮到最左边

#操作步骤

以 5 9 3 1 2 8 4 7 6 为例：

第 1 轮：从最右边开始，比较相邻两个数，右边小就交换。

  5  9  3  1  2  8  4  7 [6]   比较 7 和 6，6 < 7 → 交换
  5  9  3  1  2  8  4 [6] 7

  5  9  3  1  2  8 [4] 6  7   比较 8 和 4，4 < 8 → 交换
  5  9  3  1  2  4  8  6  7

  5  9  3  1 [2] 4  8  6  7   比较 2 和 4，2 < 4 → 不换... 
  （继续往左比较，1 会一路被「推」到最左边）

第1轮结束: 1  5  9  3  2  4  8  6  7   ← 最小值 1 归位

第 2 轮：天平移回最右边，重复操作，直到到达左边第 2 个位置。

第2轮结束: 1  2  5  9  3  4  6  8  7   ← 第 2 小的 2 归位

继续重复，直到所有数字归位：

排序完成: 1  2  3  4  5  6  7  8  9

#时间复杂度

• 第 1 轮比较 n-1 次，第 2 轮 n-2 次...第 n-1 轮 1 次
• 总比较次数：(n-1)+(n-2)+…+1 ≈ n²/2
• 交换次数与数据排列有关：已有序时 0 次，逆序时每次都要交换

#特点

• 简单易懂，是最基础的排序算法
• 稳定排序：相等的元素不会改变相对顺序
• 可以原地排序：不需要额外空间
• 速度慢，不适合大数据量
• 每轮至少把一个元素放到正确位置

#小结

• 冒泡排序从右往左比较相邻元素，小的往左浮
• 时间复杂度 O(n²)，适合小数据量或教学
• 稳定排序，原地排序