鹏展博

外观

冒泡排序

约 698 字

概述

冒泡排序（Bubble sort） 一种基础的比较排序算法。

核心思想

重复遍历数组，依次比较相邻元素，将较大值向后交换，如同气泡上浮的过程。

算法步骤

  1. 外层循环：控制遍历轮数（n-1 轮）
  2. 内层循环：比较相邻元素，将较大值后移
  3. 优化点：每轮结束后，末尾元素已有序，可减少比较范围
  4. 提前终止：当某轮无交换时，说明数组已有序，提前结束

时间复杂度

  • 在序列完全有序时，冒泡排序只需遍历一遍数组，不用执行任何交换操作，时间复杂度为 O(n)O(n)。
  • 在最坏情况下，冒泡排序要执行 (n−1)n2\frac{(n-1)n}{2} 次交换操作，时间复杂度为 O(n2)O(n^2)。
  • 冒泡排序的平均时间复杂度为 O(n2)O(n^2)。

空间复杂度

O(1)O(1)（原地排序）

稳定性

稳定（相同元素顺序不变）

伪代码

1Input. An array A consisting of n elements.2Output. A will be sorted in nondecreasing order stably.3Method. 4flag←True5while flag6flag←False7for i←1 to n−18if A[i]>A[i+1]9flag←True10Swap A[i] and A[i+1]\begin{array}{ll} 1 & \textbf{Input. } \text{An array } A \text{ consisting of }n\text{ elements.} \\ 2 & \textbf{Output. } A\text{ will be sorted in nondecreasing order stably.} \\ 3 & \textbf{Method. } \\ 4 & flag\gets True\\ 5 & \textbf{while }flag\\ 6 & \qquad flag\gets False\\ 7 & \qquad\textbf{for }i\gets1\textbf{ to }n-1\\ 8 & \qquad\qquad\textbf{if }A[i]>A[i + 1]\\ 9 & \qquad\qquad\qquad flag\gets True\\ 10 & \qquad\qquad\qquad \text{Swap } A[i]\text{ and }A[i + 1] \end{array}

实现

function bubbleSort(arr: number[]): number[] {
  const n = arr.length
  // 复制数组以避免修改原数组（可选）
  const sortedArr = [...arr]

  // 外层循环：控制遍历轮数（n-1轮）
  for (let i = 0; i < n - 1; i++) {
    let swapped = false // 优化标记

    // 内层循环：比较相邻元素（每轮减少i个已排序元素）
    for (let j = 0; j < n - 1 - i; j++) {
      // 如果前一个元素大于后一个元素
      if (sortedArr[j] > sortedArr[j + 1]) {
        // 交换元素（ES6解构赋值）
        [sortedArr[j], sortedArr[j + 1]] = [sortedArr[j + 1], sortedArr[j]]
        swapped = true // 标记发生交换
      }
    }

    // 如果本轮无交换，说明数组已有序，提前终止
    if (!swapped)
      break
  }

  return sortedArr
}

// 测试示例
const unsortedArray = [64, 34, 25, 12, 22, 11, 90]
const sortedArray = bubbleSort(unsortedArray)
console.log('排序前:', unsortedArray) // [64, 34, 25, 12, 22, 11, 90]
console.log('排序后:', sortedArray) // [11, 12, 22, 25, 34, 64, 90]

执行过程示例 （[5, 3, 8, 4]）

  • 第一轮：

    • 比较 5>35 > 3 → 交换 → [3, 5, 8, 4]
    • 比较 5<85 < 8 → 不交换
    • 比较 8>48 > 4 → 交换 → [3, 5, 4, 8]

  • 第二轮：

    • 比较 3<53 < 5 → 不交换
    • 比较 5>45 > 4 → 交换 → [3, 4, 5, 8]
    • 检查发现无交换 → 提前终止

优化

  • 优化内层循环范围

    for (let j = 0; j < n - 1 - i; j++) {
  // ...
}

    每轮结束后，末尾 i 个元素已有序，无需再比较。

  • 提前终止

    if (!swapped)
  break

    当数组在中间轮次已有序时，避免无效遍历。