冒泡排序

冒泡排序如何工作？

• 从左向右遍历, 相邻两元素逆序就交换;
• 第 n-i 轮把未排序区间 [0, i] 的最大元素送到位置 i;
• 重复 n-1 轮后整体有序;

冒泡排序如何实现？

function bubbleSort(nums: number[]): void {
  for (let i = nums.length - 1; i > 0; i--) {
    for (let j = 0; j < i; j++) {
      if (nums[j] > nums[j + 1]) {
        [nums[j], nums[j + 1]] = [nums[j + 1], nums[j]];
      }
    }
  }
}

冒泡排序的特性是什么？

• 时间复杂度: O(n^2), 该实现未做提前退出, 已有序输入仍为 O(n^2);
• 空间复杂度: O(1);
• 稳定性: 稳定排序, 只有严格逆序才交换;
• 代价: 每轮都在交换元素, 交换开销高于插入排序的元素搬移;