冒泡排序

冒泡排序不断比较相邻元素，如果顺序错误就交换它们。每一轮遍历都会把当前未排序区间的最大值“冒泡”到末尾。

实现

function bubbleSort(arr) {
  const result = [...arr]

  for (let end = result.length - 1; end > 0; end--) {
    let swapped = false

    for (let i = 0; i < end; i++) {
      if (result[i] > result[i + 1]) {
        ;[result[i], result[i + 1]] = [result[i + 1], result[i]]
        swapped = true
      }
    }

    if (!swapped) break
  }

  return result
}

复杂度

• 平均时间复杂度：O(n²)
• 最坏时间复杂度：O(n²)
• 最好时间复杂度：O(n)，数组已经有序时可提前结束
• 空间复杂度：O(1)，不计算复制输入数组的空间
• 稳定性：稳定

适合用于教学和数据规模很小的场景，不适合作为通用排序方案。