JS 实现十大排序算法（含可视化动画）

排序算法是前端面试最高频的考点之一。但大多数文章只给代码不给直观感受——你写出冒泡排序的代码，并不代表你真正理解它在做什么。

本文用 JavaScript 实现十大经典排序算法，并为每一个算法配上完整的可视化动画。你可以点击下面的播放按钮，亲眼看到每一次比较、每一次交换。

如何使用本文动画：每个算法下方都有一个可视化控件。点击 ▶ 播放 开始动画，⏸ 暂停 暂停，↻ 重置 重新生成数据，滑块调整速度。

颜色含义：

🔵 蓝色：默认状态

🟡 黄色：正在比较

🔴 红色：正在交换

🟢 绿色：已排序

排序算法总览#

算法	平均时间	最好	最坏	空间	稳定性	类型
冒泡排序	O(n²)	O(n)	O(n²)	O(1)	✅ 稳定	交换
选择排序	O(n²)	O(n²)	O(n²)	O(1)	❌ 不稳定	选择
插入排序	O(n²)	O(n)	O(n²)	O(1)	✅ 稳定	插入
希尔排序	O(n^1.3)	O(n)	O(n²)	O(1)	❌ 不稳定	插入
归并排序	O(n log n)	O(n log n)	O(n log n)	O(n)	✅ 稳定	分治
快速排序	O(n log n)	O(n log n)	O(n²)	O(log n)	❌ 不稳定	分治
堆排序	O(n log n)	O(n log n)	O(n log n)	O(1)	❌ 不稳定	选择
计数排序	O(n + k)	O(n + k)	O(n + k)	O(n + k)	✅ 稳定	非比较
桶排序	O(n + k)	O(n + k)	O(n²)	O(n + k)	✅ 稳定	非比较
基数排序	O(n × k)	O(n × k)	O(n × k)	O(n + k)	✅ 稳定	非比较

n 是数据规模，k 是值域大小。

1. 冒泡排序（Bubble Sort）#

核心思想#

依次比较相邻两个元素，如果前者大于后者就交换，每轮把最大的”冒泡”到末尾。

代码实现#

1
function bubbleSort(arr) {
2
  const n = arr.length;
3
  for (let i = 0; i < n - 1; i++) {
4
    let swapped = false;  // 优化：记录本轮是否发生交换
5
    for (let j = 0; j < n - 1 - i; j++) {
6
      if (arr[j] > arr[j + 1]) {
7
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
8
        swapped = true;
9
      }
10
    }
11
    if (!swapped) break;  // 没交换说明已经有序，提前退出
12
  }
13
  return arr;
14
}

复杂度#

时间：O(n²) | 最好 O(n)（已有序时）
空间：O(1)
稳定：✅

适用场景#

数据量极小（n < 10）或几乎有序时。实际工程中几乎不用。

可视化动画#

速度

比较：0 · 交换：0 · 就绪

2. 选择排序（Selection Sort）#

核心思想#

每轮从未排序部分找到最小值，放到已排序部分的末尾。

代码实现#

1
function selectionSort(arr) {
2
  const n = arr.length;
3
  for (let i = 0; i < n - 1; i++) {
4
    let minIdx = i;
5
    for (let j = i + 1; j < n; j++) {
6
      if (arr[j] < arr[minIdx]) {
7
        minIdx = j;
8
      }
9
    }
10
    if (minIdx !== i) {
11
      [arr[i], arr[minIdx]] = [arr[minIdx], arr[i]];
12
    }
13
  }
14
  return arr;
15
}

复杂度#

时间：O(n²)（最好和最坏都是）
空间：O(1)
稳定：❌

为什么不稳定？#

例如 [5a, 8, 5b, 2]，第一轮选最小值 2 与 5a 交换，5a 跑到了 5b 后面——稳定性被破坏。

可视化动画#

速度

比较：0 · 交换：0 · 就绪

3. 插入排序（Insertion Sort）#

核心思想#

把数组分为”已排序”和”未排序”两部分，每次从未排序部分取一个元素，插入到已排序部分的正确位置——就像打扑克时整理手牌。

代码实现#

1
function insertionSort(arr) {
2
  const n = arr.length;
3
  for (let i = 1; i < n; i++) {
4
    const cur = arr[i];
5
    let j = i - 1;
6
    while (j >= 0 && arr[j] > cur) {
7
      arr[j + 1] = arr[j];  // 向后移动
8
      j--;
9
    }
10
    arr[j + 1] = cur;  // 插入正确位置
11
  }
12
  return arr;
13
}

复杂度#

时间：O(n²) | 最好 O(n)（已有序时）
空间：O(1)
稳定：✅

适用场景#

小规模数据或部分有序数据。V8 的 Timsort 在小数组上就用插入排序。

可视化动画#

速度

比较：0 · 交换：0 · 就绪

4. 希尔排序（Shell Sort）#

核心思想#

希尔排序是插入排序的改进版。它先按一个较大的”间隔”（gap）对数组进行分组排序，然后逐步缩小 gap，最后一次 gap = 1 时退化为普通插入排序——但此时数组已经基本有序，插入排序极快。

它是第一个突破 O(n²) 的排序算法，由 Donald Shell 在 1959 年提出。

代码实现#

1
function shellSort(arr) {
2
  const n = arr.length;
3
  for (let gap = Math.floor(n / 2); gap > 0; gap = Math.floor(gap / 2)) {
4
    for (let i = gap; i < n; i++) {
5
      const cur = arr[i];
6
      let j = i - gap;
7
      while (j >= 0 && arr[j] > cur) {
8
        arr[j + gap] = arr[j];
9
        j -= gap;
10
      }
11
      arr[j + gap] = cur;
12
    }
13
  }
14
  return arr;
15
}

复杂度#

时间：O(n^1.3) ~ O(n²)（取决于 gap 序列）
空间：O(1)
稳定：❌（跨 gap 移动会破坏稳定性）

可视化动画#

速度

比较：0 · 交换：0 · 就绪

5. 归并排序（Merge Sort）#

核心思想#

经典的分治算法：

把数组对半分成两个子数组
递归排序两个子数组
合并两个有序子数组

代码实现#

1
function mergeSort(arr) {
2
  if (arr.length <= 1) return arr;
3
  const mid = Math.floor(arr.length / 2);
4
  const left = mergeSort(arr.slice(0, mid));
5
  const right = mergeSort(arr.slice(mid));
6
  return merge(left, right);
7
}
8

9
function merge(left, right) {
10
  const result = [];
11
  let i = 0, j = 0;
12
  while (i < left.length && j < right.length) {
13
    if (left[i] <= right[j]) {  // 注意 <= 保证稳定性
14
      result.push(left[i++]);
15
    } else {
16
      result.push(right[j++]);
17
    }
18
  }
19
  return [...result, ...left.slice(i), ...right.slice(j)];
20
}

原地版本（节省空间）#

1
function mergeSortInPlace(arr, left = 0, right = arr.length - 1) {
2
  if (left >= right) return;
3
  const mid = Math.floor((left + right) / 2);
4
  mergeSortInPlace(arr, left, mid);
5
  mergeSortInPlace(arr, mid + 1, right);
6
  mergeInPlace(arr, left, mid, right);
7
}
8

9
function mergeInPlace(arr, left, mid, right) {
10
  const temp = [];
11
  let i = left, j = mid + 1, k = 0;
12
  while (i <= mid && j <= right) {
13
    temp[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];
14
  }
15
  while (i <= mid) temp[k++] = arr[i++];
16
  while (j <= right) temp[k++] = arr[j++];
17
  for (let p = 0; p < temp.length; p++) {
18
    arr[left + p] = temp[p];
19
  }
20
}

复杂度#

时间：O(n log n)（所有情况）
空间：O(n)
稳定：✅

适用场景#

大规模数据
链表排序（原地合并不需要额外空间）
外部排序（数据无法全部加载到内存）

可视化动画#

速度

比较：0 · 移动：0 · 就绪

6. 快速排序（Quick Sort）#

核心思想#

也是分治：

选一个基准值（pivot）
把数组分成两部分：小于 pivot 的在左，大于 pivot 的在右
递归处理左右两部分

代码实现（简洁但占空间）#

1
function quickSortSimple(arr) {
2
  if (arr.length <= 1) return arr;
3
  const pivot = arr[0];
4
  const left = arr.slice(1).filter(x => x <= pivot);
5
  const right = arr.slice(1).filter(x => x > pivot);
6
  return [...quickSortSimple(left), pivot, ...quickSortSimple(right)];
7
}

标准实现（原地分区）#

1
function quickSort(arr, left = 0, right = arr.length - 1) {
2
  if (left >= right) return arr;
3
  const pivotIdx = partition(arr, left, right);
4
  quickSort(arr, left, pivotIdx - 1);
5
  quickSort(arr, pivotIdx + 1, right);
6
  return arr;
7
}
8

9
function partition(arr, left, right) {
10
  const pivot = arr[right];  // 选最右为基准
11
  let i = left - 1;
12
  for (let j = left; j < right; j++) {
13
    if (arr[j] <= pivot) {
14
      i++;
15
      [arr[i], arr[j]] = [arr[j], arr[i]];
16
    }
17
  }
18
  [arr[i + 1], arr[right]] = [arr[right], arr[i + 1]];
19
  return i + 1;
20
}

优化：三数取中 + 三路快排#

1
// 三数取中：选 left, mid, right 三个值的中位数为 pivot
2
function medianOfThree(arr, left, right) {
3
  const mid = Math.floor((left + right) / 2);
4
  if (arr[left] > arr[mid]) [arr[left], arr[mid]] = [arr[mid], arr[left]];
5
  if (arr[left] > arr[right]) [arr[left], arr[right]] = [arr[right], arr[left]];
6
  if (arr[mid] > arr[right]) [arr[mid], arr[right]] = [arr[right], arr[mid]];
7
  [arr[mid], arr[right - 1]] = [arr[right - 1], arr[mid]];
8
  return arr[right - 1];
9
}
10

11
// 三路快排：处理大量重复元素
12
function quickSort3Way(arr, left = 0, right = arr.length - 1) {
13
  if (left >= right) return;
14
  let lt = left, gt = right, i = left + 1;
15
  const pivot = arr[left];
16
  while (i <= gt) {
17
    if (arr[i] < pivot) {
18
      [arr[lt], arr[i]] = [arr[i], arr[lt]];
19
      lt++; i++;
20
    } else if (arr[i] > pivot) {
21
      [arr[i], arr[gt]] = [arr[gt], arr[i]];
22
      gt--;
23
    } else {
24
      i++;
25
    }
26
  }
27
  quickSort3Way(arr, left, lt - 1);
28
  quickSort3Way(arr, gt + 1, right);
29
}

复杂度#

时间：平均 O(n log n) | 最坏 O(n²)（已有序时选首尾为 pivot）
空间：O(log n)（递归栈）
稳定：❌

为什么最坏 O(n²)？#

如果每次选到的 pivot 都是最小或最大值，分区会极不均匀。三数取中可以大幅降低这种概率。

可视化动画#

速度

比较：0 · 交换：0 · 就绪

7. 堆排序（Heap Sort）#

核心思想#

利用最大堆的性质：

把数组构建成最大堆（父节点 ≥ 子节点）
把堆顶（最大值）和最后一个元素交换
把堆大小减 1，重新调整堆
重复直到堆为空

代码实现#

1
function heapSort(arr) {
2
  const n = arr.length;
3

4
  // 1. 构建最大堆（从最后一个非叶子节点开始下沉）
5
  for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
6
    heapify(arr, n, i);
7
  }
8

9
  // 2. 依次取出最大值
10
  for (let i = n - 1; i > 0; i--) {
11
    [arr[0], arr[i]] = [arr[i], arr[0]];  // 堆顶与末尾交换
12
    heapify(arr, i, 0);  // 调整剩余堆
13
  }
14
  return arr;
15
}
16

17
function heapify(arr, n, i) {
18
  let largest = i;
19
  const left = 2 * i + 1;
20
  const right = 2 * i + 2;
21

22
  if (left < n && arr[left] > arr[largest]) largest = left;
23
  if (right < n && arr[right] > arr[largest]) largest = right;
24

25
  if (largest !== i) {
26
    [arr[i], arr[largest]] = [arr[largest], arr[i]];
27
    heapify(arr, n, largest);  // 递归向下调整
28
  }
29
}

复杂度#

时间：O(n log n)（所有情况）
空间：O(1)
稳定：❌

适用场景#

需要 O(1) 空间 + O(n log n) 时间
Top K 问题：维护大小为 K 的堆，求最大/最小 K 个元素

可视化动画#

速度

比较：0 · 交换：0 · 就绪

8. 计数排序（Counting Sort）#

核心思想#

非比较排序。统计每个值出现的次数，然后按次数顺序输出。

代码实现#

1
function countingSort(arr) {
2
  if (arr.length === 0) return arr;
3
  const min = Math.min(...arr);
4
  const max = Math.max(...arr);
5
  const count = new Array(max - min + 1).fill(0);
6

7
  // 统计每个值的频次
8
  for (const num of arr) {
9
    count[num - min]++;
10
  }
11

12
  // 累加，count[i] 表示 ≤ i 的元素个数（为了稳定性）
13
  for (let i = 1; i < count.length; i++) {
14
    count[i] += count[i - 1];
15
  }
16

17
  // 从后往前遍历原数组，放到正确位置
18
  const result = new Array(arr.length);
19
  for (let i = arr.length - 1; i >= 0; i--) {
20
    count[arr[i] - min]--;
21
    result[count[arr[i] - min]] = arr[i];
22
  }
23
  return result;
24
}

复杂度#

时间：O(n + k)（k = max - min）
空间：O(n + k)
稳定：✅

适用场景与限制#

✅ 整数排序
✅ 值域较小（k ≤ n）
❌ 浮点数或字符串直接用不了
❌ 值域极大会爆内存（比如排序 [1, 1000000000] 需要 10 亿个槽位）

可视化动画#

速度

操作：0 · 写入：0 · 就绪

9. 桶排序（Bucket Sort）#

核心思想#

把数据分到若干个桶，每个桶内部分别排序，最后按桶顺序合并。

代码实现#

1
function bucketSort(arr, bucketSize = 5) {
2
  if (arr.length === 0) return arr;
3
  const min = Math.min(...arr);
4
  const max = Math.max(...arr);
5
  const bucketCount = Math.floor((max - min) / bucketSize) + 1;
6
  const buckets = Array.from({ length: bucketCount }, () => []);
7

8
  // 分桶
9
  for (const num of arr) {
10
    const idx = Math.floor((num - min) / bucketSize);
11
    buckets[idx].push(num);
12
  }
13

14
  // 桶内排序 + 合并
15
  const result = [];
16
  for (const bucket of buckets) {
17
    if (bucket.length > 0) {
18
      bucket.sort((a, b) => a - b);  // 桶内可以用任意排序
19
      result.push(...bucket);
20
    }
21
  }
22
  return result;
23
}

复杂度#

时间：平均 O(n + k) | 最坏 O(n²)（所有数据落入同一桶）
空间：O(n + k)
稳定：✅（如果桶内排序稳定）

适用场景#

数据均匀分布
浮点数排序（计数排序处理不了）

可视化动画#

速度

操作：0 · 写入：0 · 就绪

10. 基数排序（Radix Sort）#

核心思想#

按位排序。先按个位排，再按十位排，再按百位排，直到最高位。

代码实现#

1
function radixSort(arr) {
2
  if (arr.length === 0) return arr;
3
  const max = Math.max(...arr);
4
  const maxDigit = String(max).length;
5

6
  for (let digit = 0; digit < maxDigit; digit++) {
7
    // 用 10 个桶（0-9）
8
    const buckets = Array.from({ length: 10 }, () => []);
9
    for (const num of arr) {
10
      const d = Math.floor(num / Math.pow(10, digit)) % 10;
11
      buckets[d].push(num);
12
    }
13
    arr = [].concat(...buckets);
14
  }
15
  return arr;
16
}

复杂度#

时间：O(n × k)（k = 最大数的位数）
空间：O(n + k)
稳定：✅

LSD vs MSD#

LSD（最低位优先）：从个位开始，常用
MSD（最高位优先）：从最高位开始，适合字符串

可视化动画#

速度

操作：0 · 写入：0 · 就绪

进阶：JavaScript `Array.prototype.sort()` 内部用什么算法？#

这是面试官最爱的”补刀题”。

V8 引擎（Chrome / Node.js）#

Node.js 12 / Chrome 70 之前：

数组长度 ≤ 10：插入排序
数组长度 > 10：快速排序

Node.js 12 / Chrome 70 之后：

V8 切换到了 Timsort——一种混合排序算法，由 Tim Peters 在 2002 年为 Python 设计。

Timsort 原理#

Timsort 是 归并排序 + 插入排序的混合体，专门优化”现实世界中的数据”——这些数据往往部分有序。

核心步骤：

扫描数组，找到自然有序的”run”（递增或递减序列）
短 run 用插入排序扩展到最小长度（minrun，通常 32-64）
将 run 压栈，按特定规则合并相邻 run
**使用 galloping mode（疾驰模式）**加速合并

为什么 Timsort 这么快？#

最坏 O(n log n)：和归并排序一样
最好 O(n)：已有序时只需扫描一遍
稳定：✅
现实数据快：因为大部分真实数据是部分有序的

各引擎对比#

引擎	算法
V8（Chrome / Node.js）	Timsort
SpiderMonkey（Firefox）	Merge Sort（自适应）
JavaScriptCore（Safari）	Merge Sort
Chakra（旧 Edge）	Quick Sort + Insertion

结论：现代浏览器的 Array.sort 都是稳定的（ECMAScript 2019 已强制要求）。

sort 的坑#

坑 1：默认按字符串排序

1
[10, 1, 20, 2].sort()
2
// [1, 10, 2, 20] ❌ 不是数字顺序
3
// 因为默认调用 toString() 后按 UTF-16 比较
4

5
[10, 1, 20, 2].sort((a, b) => a - b)
6
// [1, 2, 10, 20] ✅

坑 2：sort 是原地修改

1
const arr = [3, 1, 2];
2
const sorted = arr.sort();
3
console.log(arr);    // [1, 2, 3] ❗ 原数组被修改
4
console.log(sorted === arr);  // true ❗ 返回同一个引用

ES2023 引入了 toSorted()，返回新数组：

1
const arr = [3, 1, 2];
2
const sorted = arr.toSorted();
3
console.log(arr);     // [3, 1, 2] ✅ 原数组不变
4
console.log(sorted);  // [1, 2, 3]

面试常见问题#

Q1: 哪些排序是稳定的？#

口诀：「冒插归计桶基稳，选希快堆不稳」

✅ 稳定：冒泡、插入、归并、计数、桶、基数
❌ 不稳定：选择、希尔、快排、堆

Q2: 为什么”稳定”很重要？#

多字段排序场景。比如先按年龄排，再按姓名排——如果第二次排序不稳定，会破坏第一次的结果。

1
// 先按 age 排，再按 name 排
2
arr.sort((a, b) => a.age - b.age);
3
arr.sort((a, b) => a.name.localeCompare(b.name));
4
// 如果 sort 稳定，结果是按 name 排序，相同 name 内按 age 排序

Q3: O(n log n) 是比较排序的下界吗？#

是的。比较排序的本质是决策树，n 个元素有 n! 种排列，决策树高度至少 log(n!) ≈ n log n。

要突破这个下界，必须不依赖比较——这就是计数、桶、基数排序能达到 O(n) 的原因。

Q4: 海量数据排序怎么办？#

数据放不下内存 → 外部排序（多路归并）
求 Top K → 大小为 K 的堆（O(n log K)）
整数 + 值域小 → 计数排序
数据均匀分布 → 桶排序

Q5: 100 亿个数找出最大的 100 个怎么做？#

经典 Top K 问题：

维护一个大小为 100 的最小堆
遍历所有数：
- 如果当前数 > 堆顶，弹出堆顶，插入当前数
- 否则跳过
最后堆中就是最大的 100 个

时间复杂度：O(n log 100) = O(n)，空间 O(100) = O(1)。

Q6: 手写一个稳定的快速排序#

标准快排不稳定，但可以用额外空间换稳定性：

1
function stableQuickSort(arr) {
2
  if (arr.length <= 1) return arr;
3
  const pivot = arr[0];
4
  const left = [], equal = [], right = [];
5
  for (const x of arr) {
6
    if (x < pivot) left.push(x);
7
    else if (x > pivot) right.push(x);
8
    else equal.push(x);
9
  }
10
  return [...stableQuickSort(left), ...equal, ...stableQuickSort(right)];
11
}

注意：用 filter 或显式遍历保持原始顺序就能保证稳定性。

Q7: 给一个几乎有序的数组（每个元素离正确位置不超过 k 个位置），最快排序方法？#

用大小为 k+1 的最小堆：

把前 k+1 个元素入堆
从第 k+2 个开始：弹出堆顶（这就是当前最小值），插入新元素
最后依次弹出堆中元素

时间复杂度：O(n log k)。当 k 远小于 n 时远快于通用排序。

总结#

排序算法考的不是”背代码”，而是根据场景选择合适算法的能力：

场景	推荐算法
通用场景	Timsort / Array.sort
数据量小（n < 16）	插入排序
数据基本有序	插入排序 / Timsort
大规模 + 稳定	归并排序
大规模 + 原地	堆排序
大规模 + 平均最快	快速排序（三数取中）
整数 + 值域小	计数排序
浮点数 + 均匀分布	桶排序
整数 + 位数固定	基数排序
Top K	堆
外部排序	多路归并

排序算法是算法世界的”Hello World”——简单到能在纸上写出来，深入到能看出一个工程师的思维方式。希望本文的可视化能让你真正”看见”算法，而不只是背诵代码。

主要参考资料：

Thomas H. Cormen 《Introduction to Algorithms》（CLRS 算法导论）
Robert Sedgewick 《Algorithms, 4th Edition》
《剑指 Offer》《算法竞赛入门经典》
V8 官方博客：Getting things sorted in V8
ECMAScript 2019 规范关于 Array.sort 稳定性的修订
Tim Peters 《Timsort》原始论文（CPython 源码）
VisuAlgo（https://visualgo.net/）
MDN: Array.prototype.sort

排序算法总览#

1. 冒泡排序（Bubble Sort）#

核心思想#

代码实现#

复杂度#

适用场景#

可视化动画#

2. 选择排序（Selection Sort）#

核心思想#

代码实现#

复杂度#

为什么不稳定？#

可视化动画#

3. 插入排序（Insertion Sort）#

核心思想#

代码实现#

复杂度#

适用场景#

可视化动画#

4. 希尔排序（Shell Sort）#

核心思想#

代码实现#

复杂度#

可视化动画#

5. 归并排序（Merge Sort）#

核心思想#

代码实现#

原地版本（节省空间）#

复杂度#

适用场景#

可视化动画#

6. 快速排序（Quick Sort）#

核心思想#

代码实现（简洁但占空间）#

标准实现（原地分区）#

优化：三数取中 + 三路快排#

复杂度#

为什么最坏 O(n²)？#

可视化动画#

7. 堆排序（Heap Sort）#

核心思想#

代码实现#

复杂度#

适用场景#

可视化动画#

8. 计数排序（Counting Sort）#

核心思想#

代码实现#

复杂度#

适用场景与限制#

可视化动画#

9. 桶排序（Bucket Sort）#

核心思想#

代码实现#

复杂度#

适用场景#

可视化动画#

10. 基数排序（Radix Sort）#

核心思想#

代码实现#

复杂度#

LSD vs MSD#

可视化动画#

进阶：JavaScript Array.prototype.sort() 内部用什么算法？#

V8 引擎（Chrome / Node.js）#

Timsort 原理#

为什么 Timsort 这么快？#

各引擎对比#

sort 的坑#

面试常见问题#

Q1: 哪些排序是稳定的？#

Q2: 为什么”稳定”很重要？#

Q3: O(n log n) 是比较排序的下界吗？#

Q4: 海量数据排序怎么办？#

Q5: 100 亿个数找出最大的 100 个怎么做？#

Q6: 手写一个稳定的快速排序#

Q7: 给一个几乎有序的数组（每个元素离正确位置不超过 k 个位置），最快排序方法？#

总结#

进阶：JavaScript `Array.prototype.sort()` 内部用什么算法？#