算法图谱

Bubble Sort

冒泡排序

排序入门时间 O(n²)空间 O(1)

反复比较相邻元素，大的往后冒。每轮把当前最大值送到右端。

动画

7
2
9
4
1
8
5
3

冒泡排序：相邻比较，大的往后冒。

1 / 51

  • 默认

讲解

最容易演示交换与有序区的入门排序，帮助建立「比较排序」的直觉。

  1. 01从左到右比较 a[i] 与 a[i+1]，逆序则交换。
  2. 02一轮结束后，最大元素沉到末尾，有序区扩大一格。
  3. 03若整轮没有交换，提前结束。

易错点

  • 教学用途为主，实际几乎不用。
  • 忘记缩小无序区会导致重复比较已排好的尾部。

代码

function bubbleSort(a) {
  for (let end = a.length - class="text-accent">1; end > class="text-accent">0; end--) {
    let swapped = false;
    for (let i = class="text-accent">0; i < end; i++) {
      if (a[i] > a[i + class="text-accent">1]) {
        [a[i], a[i + class="text-accent">1]] = [a[i + class="text-accent">1], a[i]];
        swapped = true;
      }
    }
    if (!swapped) break;
  }
  return a;
}

相关课题