排序算法图解

6 大经典排序，一步一步看图理解——每个算法配有 SVG 动态图解 + 生活类比 + 代码对照

冒泡排序 选择排序 插入排序 快速排序 归并排序 堆排序
① 冒泡排序 ② 选择排序 ③ 插入排序 ④ 快速排序 ⑤ 归并排序 ⑥ 堆排序 ⑦ 终极对比 ⑧ 面试高频

🎨 图解颜色约定（全文统一）

正在比较
正在交换
当前位置/哨兵
已排好（最终位置）
未处理
① 冒泡排序 Bubble Sort
最直觉的排序——相邻的比，大的往后冒
🫧 类比：水中气泡从底往上冒

🎯 想象一杯碳酸饮料：小气泡从杯底慢慢往上浮，越大的气泡浮得越快。

🔢 数组就是一杯水：每一轮，拿相邻两个数比较，大的往右"冒"（交换），一轮下来最大的就"浮"到了最右端。

🔁 重复 n-1 轮：每轮把当前最大的泡泡送到它该在的位置。

冒泡排序：[5, 3, 8, 1, 2] → [1, 2, 3, 5, 8] 第 1 轮 5 3 8 1 2 ← 比较 5>3，交换! 3 5 8 1 2 ← 比较 5<8，不交换 3 5 8 1 2 ← 比较 8>1，交换! 3 5 1 8 2 ← 比较 8>2，交换! 3 5 1 2 8 ✅ 最大值 8 到位! 第 2 轮 3 5 1 2 8 3<5，不交换 3 5 1 2 8 5>1，交换! 最终结果 1 2 3 5 8
冒泡排序完整过程（简化展示前 2 轮 + 最终结果，实际需要 4 轮）
Explorer
📂 sort/
BubbleSort.js
SelectionSort.js
QuickSort.js
function bubbleSort(arr) { // 外层：控制轮数，n 个元素最多 n-1 轮 for (let i = 0; i < arr.length - 1; i++) { // 内层：每轮从左到右，相邻比较 // 每轮结束后，最右边的 i+1 个已排好 for (let j = 0; j < arr.length - 1 - i; j++) { if (arr[j] > arr[j + 1]) { // ← 相邻比较 let temp = arr[j]; // ← 交换三步曲 arr[j] = arr[j + 1]; arr[j + 1] = temp; } } } }

📊 复杂度分析

最好 O(n) — 已经有序 平均 O(n²) 最差 O(n²) — 逆序 空间 O(1)

✅ 稳定排序：相等元素不交换，相对顺序不变

💡 最好 O(n) 需加优化：如果某轮没有任何交换，说明已有序，直接退出

实战总结 冒泡排序面试必考但实战几乎不用——O(n²) 太慢。唯一用处：理解"排序"这个概念的第一步，以及几乎有序数据的微调（加 early-exit 优化后接近 O(n)）。
② 选择排序 Selection Sort
每轮选最小的放前面——像挑苹果，先挑最好的
🍎 类比：从果篮里挑苹果

🎯 一篮苹果排排坐：你想按大小摆好，怎么选？

🔍 第一轮：扫一遍所有苹果，挑出最小的那个，放到第 1 个位置。

🔍 第二轮：从剩下的苹果里，再挑最小的，放到第 2 个位置。

🔁 重复 n-1 次：每次只选一个最小值放到前面，直到全部排好。

💡 和冒泡的区别：冒泡是"相邻交换"，选择是"找到最小再一次性交换"，每轮最多交换 1 次。

选择排序：[5, 3, 8, 1, 2] → [1, 2, 3, 5, 8] 第 1 轮：找最小值 5 3 8 1 2 ← 扫描全部，最小=1 交换位置 0 和 3 1 3 8 5 2 ✅ 1 到位! 第 2 轮：从位置 1 开始找最小 1 3 8 5 2 ← 最小=2 交换位置 1 和 4 1 2 8 5 3 ✅ 2 到位! 继续… 最终结果 1 2 3 5 8
选择排序：每轮扫描找最小值，交换到前面（每轮只有 1 次交换）
Explorer
📂 sort/
BubbleSort.js
SelectionSort.js
QuickSort.js
function selectionSort(arr) { for (let i = 0; i < arr.length - 1; i++) { let minIndex = i; // ← 假设当前位置最小 for (let j = i + 1; j < arr.length; j++) { if (arr[j] < arr[minIndex]) { // ← 找更小的 minIndex = j; } } // 一轮结束，交换一次 if (minIndex !== i) { // ← 优化：位置没变就不换 let temp = arr[i]; arr[i] = arr[minIndex]; arr[minIndex] = temp; } } }

📊 复杂度分析

最好 O(n²) 平均 O(n²) 最差 O(n²) 空间 O(1)

❌ 不稳定排序：例如 [5, 5, 3]，交换 5 和 3 时两个 5 的相对顺序可能改变

💡 不管数据是否有序，比较次数都一样，永远 O(n²)——因为每轮都要全部扫描一遍

⚠️ 什么场景不要用选择排序？

❌ 数据量大时（O(n²) 太慢）

❌ 需要稳定排序时（选择排序不稳定）

❌ 数据几乎有序时（选择排序无法利用"几乎有序"的优势）

实战总结 选择排序唯一的优点：交换次数最少（每轮最多 1 次）。适合交换代价很大的场景（如排序的是大对象/文件指针）。其他场景用快排或归并。
③ 插入排序 Insertion Sort
像打扑克牌——摸一张，插到手里合适的位置
🃏 类比：打扑克牌的摸牌过程

🎴 你手里已经有几张牌：3、5、8，按顺序排好。

🆕 摸到一张新牌"1"：从右往左比，8>1→5>1→3>1→插到最前面！

🆕 再摸到"6"：从右往左比，8>6→5<6→插到 5 和 8 之间！

💡 关键思想：左侧始终是有序区，新元素从右往左找到自己该插入的位置。

插入排序：[5, 3, 8, 1, 2] → [1, 2, 3, 5, 8] 第 1 步：插入 3 5 3 8 1 2 ← 3 和 5 比，3<5，5右移 有序区 3 5 8 1 2 ✅ [3,5]有序 第 2 步：插入 8 3 5 8 1 2 ← 8>5，直接放在原位 第 3 步：插入 1（需要一路左移） 3 5 8 1 2 1<8→1<5→1<3，一路左移! 1 3 5 8 2 ✅ [1,3,5,8]有序 最终结果 1 2 3 5 8
插入排序：左侧始终有序，新元素从右往左找位置插入
Explorer
📂 sort/
BubbleSort.js
SelectionSort.js
InsertionSort.js
function insertionSort(arr) { for (let i = 1; i < arr.length; i++) { let key = arr[i]; // ← 当前要插入的牌 let j = i - 1; // 从右往左找：比 key 大的都右移 while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; // ← 右移（让位） j--; } arr[j + 1] = key; // ← 插入到正确位置 } }

📊 复杂度分析

最好 O(n) — 已经有序 平均 O(n²) 最差 O(n²) — 逆序 空间 O(1)

✅ 稳定排序：相等元素不移动，相对顺序不变

💡 插入排序是对"几乎有序"数据最快的 O(n²) 排序——如果数据本身基本有序，while 循环几乎不执行，接近 O(n)

💡 插入排序的实战价值

✅ JavaScript 引擎的 Array.prototype.sort() 对小数组用插入排序

✅ TimSort（Python/JS 默认排序）用插入排序处理小片段

✅ 适合数据量小或几乎有序的场景

实战总结 插入排序是 O(n²) 排序里实战价值最大的——很多高级排序（快排、归并、TimSort）在分治到小段时都会切回插入排序。面试常考"为什么快排里小段用插入排序"。
④ 快速排序 Quick Sort
分治之王——选一个标杆，小的放左大的放右，递归继续
🏃 类比：体育课按身高排队

📏 老师喊：1米7的站出来当标杆! 比1米7矮的站左边，高的站右边。

🔁 左边那组再来一次：1米5的当标杆，矮的左边，高的右边。

🔁 右边那组也来一次：1米8的当标杆……

✅ 每组只剩1个人时：排好了！所有人从左到右就是按身高排的。

💡 关键操作 = 分区（partition）：选标杆 + 分两边 = 一轮分区

快速排序：[5, 3, 8, 1, 2]，选末尾元素为 pivot 第 1 次分区：pivot = 2（最后一个元素） 5 3 8 1 2 ← pivot=2 分区结果 1 2 5 3 8 ≤pivot pivot >pivot 左边 [1]：只剩1个，已排好 ✅ 右边 [5,3,8]，pivot = 8 5 3 8 ← pivot=8 分区结果 5 3 8 ≤8 pivot [5,3]，pivot = 3 5 3 5>3，交换→[3,5] 最终结果 1 2 3 5 8 递归树 [5,3,8,1,2] p=2 [1] ✅ [5,3,8] p=8 [5,3] p=3 [] ✅ [3] ✅ [5] ✅
快速排序：每次选 pivot 分区，递归处理两边（右侧展示递归树）
Explorer
📂 sort/
BubbleSort.js
SelectionSort.js
QuickSort.js
function quickSort(arr, low, high) { if (low < high) { let pi = partition(arr, low, high); // ← 分区 quickSort(arr, low, pi - 1); // ← 排左边 quickSort(arr, pi + 1, high); // ← 排右边 } } // 核心：分区函数（Lomuto 方案） function partition(arr, low, high) { let pivot = arr[high]; // ← 选最后一个当 pivot let i = low - 1; // ← i 指向"≤pivot 区"的末尾 for (let j = low; j < high; j++) { if (arr[j] <= pivot) { i++; swap(arr, i, j); // ← 交换到左边区 } } swap(arr, i + 1, high); // ← pivot 放到中间 return i + 1; // ← 返回 pivot 最终位置 }

📊 复杂度分析

最好 O(n log n) — 每次均分 平均 O(n log n) 最差 O(n²) — 每次选到最大/最小 空间 O(log n) — 递归栈

❌ 不稳定排序：分区时交换可能改变相等元素的相对顺序

⚠️ 快排退化问题

如果每次 pivot 都选到最大/最小值，就变成 O(n²)——等于每个元素都要和所有其他元素比较一遍！

💡 解决方案：① 随机选 pivot ② 三数取中（arr[low]+arr[mid]+arr[high]的中位数）③ 小段切插入排序

实战总结 快排是面试最常考的排序——考频率远超其他排序。JavaScript 的 Array.prototype.sort() 在 V8 引擎中使用 TimSort（归并+插入的混合）。实际项目直接调库，但面试要能手写 partition。
⑤ 归并排序 Merge Sort
先拆到单个，再两两合并——分治的另一个经典
📚 类比：合并两叠已排好的试卷

📝 老师收了两叠试卷：A 叠 [1,4,7]，B 叠 [2,3,9]，各叠已经按学号排好。

🔗 怎么合并成一叠？拿 A 的第一张和 B 的第一张比，小的放下来，再比下一张……

1<2→放1，4>2→放2，4>3→放3，4<9→放4，7<9→放7，最后放9 → [1,2,3,4,7,9]

💡 归并排序 = 先拆 + 再合：拆到每组1个（天然有序），再两两合并。

归并排序：[5,3,8,1] → [1,3,5,8] 拆分阶段（自顶向下） [5, 3, 8, 1] [5, 3] [8, 1] [5] [3] [8] [1] ← 单个=有序 合并阶段（自底向上） [5] + [3] → [3, 5] 3<5→放3→放5 [8] + [1] → [1, 8] 1<8→放1→放8 [3, 5] + [1, 8] → [1, 3, 5, 8] 3>1→放1, 3<8→放3, 5<8→放5, 放8 合并细节（双指针法） 左指针→[3,5] 右指针→[1,8] 结果→[] i=0,j=0: 3>1→放1 | i=0,j=1: 3<8→放3 | i=1,j=1: 5<8→放5 | 放8 → [1,3,5,8] ✅
归并排序：先拆分到单个元素，再两两合并成有序数组
Explorer
📂 sort/
QuickSort.js
MergeSort.js
HeapSort.js
function mergeSort(arr, temp, left, right) { if (left >= right) return; // ← 递归终止 let mid = left + Math.floor((right - left) / 2); // ← 防溢出写法 mergeSort(arr, temp, left, mid); // ← 排左半 mergeSort(arr, temp, mid + 1, right); // ← 排右半 merge(arr, temp, left, mid, right); // ← 合并两半 } // 合并两个有序数组 function merge(arr, temp, left, mid, right) { let i = left, j = mid + 1, k = left; while (i <= mid && j <= right) { if (arr[i] <= arr[j]) temp[k++] = arr[i++]; // ← 左小取左 else temp[k++] = arr[j++]; // ← 右小取右 } while (i <= mid) temp[k++] = arr[i++]; // ← 左边剩余 while (j <= right) temp[k++] = arr[j++]; // ← 右边剩余 for (i = left; i <= right; i++) arr[i] = temp[i]; // ← 拷贝回原数组 }

📊 复杂度分析

最好 O(n log n) 平均 O(n log n) 最差 O(n log n) 空间 O(n) — 需要辅助数组

✅ 稳定排序：合并时相等元素先取左边的，相对顺序不变

💡 归并排序的复杂度与数据分布无关——永远 O(n log n)，不会退化！

💡 归并排序的实战价值

✅ JavaScript 的 Array.prototype.sort() 在 V8 引擎中使用 TimSort（归并+插入的混合）

✅ 需要稳定排序且保证 O(n log n) 时的首选

✅ 适合链表排序（不需要随机访问，归并天然适合）

✅ 外部排序（数据大到内存放不下）的核心算法

实战总结 归并排序最大的缺点是空间 O(n)，不适合内存敏感场景。但它是唯一保证 O(n log n) 且稳定的排序。面试高频题：为什么 JavaScript 的 Array.prototype.sort() 用 TimSort？因为 TimSort 是归并+插入的混合，保证稳定且高效——对象需要稳定排序（equals 相等的对象不应改变顺序）。
⑥ 堆排序 Heap Sort
用堆这种数据结构——先建大顶堆，再一个个取最大值
🏔️ 类比：公司选拔 CEO

🏢 公司是一棵树：CEO 在最顶端（根节点），下面是各部门经理（子节点）。

📋 大顶堆规则：每个经理的能力 ≤ 他上级的能力。所以 CEO 一定是能力最强的人。

🏆 选最牛的人：CEO（堆顶）就是最大值！拿走他。

🔁 谁顶上来？：把最底层最后一个人放堆顶，然后"下沉"——让他和下属比，不如就换下来，直到合适的位置。

💡 堆排序 = 建堆 + 循环（取堆顶 → 末尾元素上堆顶 → 下沉调整）

堆排序：[5,3,8,1,2] → [1,2,3,5,8] 第 1 步：建大顶堆 8 3 5 1 2 大顶堆性质： 父节点 ≥ 子节点 根节点 = 最大值 数组形式： 8 3 5 1 2 [0] [1] [2] [3] [4] 第 2 步：取堆顶 8，和末尾 2 交换，然后下沉调整 2 3 5 1 8 ← 2上堆顶，8已排好 5 3 2 1 8 ← 2下沉：2<5→换，2<3→换 第 3 步：取堆顶 5，交换+下沉 1 2 3 5 8 ✅ 排序完成! 核心操作 1. 建堆：从最后一个非叶节点 开始，从右到左逐个下沉 2. 取堆顶：最大值，和末尾交换 3. 下沉：新堆顶可能不满足 大顶堆性质，需要往下调整
堆排序：建大顶堆 → 取堆顶（最大值）→ 交换到末尾 → 下沉调整 → 重复
Explorer
📂 sort/
MergeSort.js
HeapSort.js
📂 heap/
MaxHeap.js
function heapSort(arr) { let n = arr.length; // 1. 建大顶堆（从最后一个非叶节点开始下沉） for (let i = Math.floor(n / 2) - 1; i >= 0; i--) { siftDown(arr, n, i); // ← 下沉调整 } // 2. 逐个取最大值放末尾 for (let i = n - 1; i > 0; i--) { swap(arr, 0, i); // ← 堆顶和末尾交换 siftDown(arr, i, 0); // ← 堆顶下沉（范围缩小到i） } } // 下沉操作：让 arr[i] 在 [0,n) 范围内下沉到正确位置 function siftDown(arr, n, i) { while (2 * i + 1 < n) { // ← 有左子节点 let larger = 2 * i + 1; // ← 先假设左子更大 if (larger + 1 < n && arr[larger + 1] > arr[larger]) larger++; // ← 右子更大就换右子 if (arr[i] >= arr[larger]) break; // ← 已满足堆性质 swap(arr, i, larger); // ← 下沉 i = larger; } }

📊 复杂度分析

最好 O(n log n) 平均 O(n log n) 最差 O(n log n) 空间 O(1)

❌ 不稳定排序：下沉操作可能改变相等元素的相对顺序

💡 建堆过程本身是 O(n)，不是 O(n log n)！这是一个常见的面试陷阱题

💡 建堆为什么是 O(n)？

直觉上以为每个元素下沉 O(log n) × n 个 = O(n log n)，但其实：底层节点多但下沉少，顶层节点少但下沉多。数学证明总比较次数 ≈ 2n，所以建堆是 O(n)。

实战总结 堆排序最大优势 = 空间 O(1) + 时间保证 O(n log n)——比快排最差 O(n²) 好，比归并空间 O(n) 好。但实际用得不多，因为缓存不友好（跳跃式访问数组），常数项大。堆这个数据结构本身更有用——PriorityQueue、Top-K 问题、定时任务调度等。
⑦ 终极对比：6 大排序一表看清
面试最常问的对比——一眼看出每个算法的特点和适用场景
算法 最好 平均 最差 空间 稳定 一句话总结
冒泡排序 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 log n) O(n log n) O(n²) O(log n) ❌ 实战最常用，面试必考
归并排序 O(n log n) O(n log n) O(n log n) O(n) ✅ 稳定+保证 O(n log n)
堆排序 O(n log n) O(n log n) O(n log n) O(1) ❌ 原地+保证 O(n log n)

🎯 面试速记口诀

冒泡选择插入 → O(n²) 三兄弟

快归堆 → O(n log n) 三剑客

稳定排序 → 冒泡 ✅ 插入 ✅ 归并 ✅

不稳定排序 → 选择 ❌ 快排 ❌ 堆排 ❌

空间 O(1) → 冒泡、选择、插入、堆排（原地排序）

空间 O(n) → 归并（需要辅助数组）

排序算法选择决策树 数据量大吗？（n > 1000） 小数据 几乎有序？ → 插入排序 是 → O(n) 否 → O(n²)但简单 大数据 需要稳定排序？ 需要 归并排序 不需要 内存敏感？ 堆排序 O(1) 快排 O(log n) 💡 实际项目 99% 场景：直接调 arr.sort()，底层引擎已经帮你选好了！
排序算法选择决策树：根据数据规模和需求快速决策
⑧ 面试高频问题
排序相关的面试题——理解了图解，这些都不难
Q1：为什么快排平均比归并快？

快排的常数因子更小：

① 快排是原地排序（不需要辅助数组），归并每次合并都要拷贝 → 快排缓存更友好

② 快排的分区操作是顺序扫描（CPU 缓存命中率高），归并是两个数组交替比较 → 快排实际运行更快

③ 虽然最差 O(n²)，但随机化 pivot 后概率极低，平均 O(n log n) 的常数项约是归并的 60%~70%

Q2：Array.prototype.sort() 底层用的什么排序？

V8 引擎（Chrome/Node.js）→ TimSort（归并+插入的混合排序）

SpiderMonkey（Firefox）→ 归并排序的变体

💡 为什么用 TimSort？因为需要稳定排序——equals() 相等的对象不应改变顺序，快排不稳定。

Q3：什么是排序的稳定性？什么时候重要？

稳定性：如果两个元素值相等，排序后它们的相对顺序和排序前一样，就是稳定的。

举例：学生列表先按分数排序，再按班级排序。如果排序稳定，同一个班的学生仍保持分数有序。

💡 什么时候重要：多次排序、数据库 ORDER BY 多列、对象排序时。

Q4：快排怎么优化？

① 随机化 pivot：避免最差情况（已排序/逆序数组退化到 O(n²)）

② 三数取中：取 arr[low]、arr[mid]、arr[high] 的中位数当 pivot

③ 小段切插入排序：子数组长度较小时用插入排序（TimSort 就这么做的）

④ 三路快排：大量重复元素时，把 =pivot 的元素集中到中间，避免重复比较

⑤ 尾递归优化：较短的子数组递归，较长的用循环 → 递归深度降到 O(log n)

Q5：堆排序和快排都是 O(n log n)，为什么实战快排更常用？

① 缓存不友好：堆排序是跳跃式访问（父→子：i→2i+1），CPU 缓存命中率低

② 常数项大：堆排序的 swap 次数比快排多

③ 不稳定：和快排一样不稳定，但比快排慢，优势只剩"保证 O(n log n)"

💡 但堆排序在Top-K 问题（只需前 K 大/小）中非常有用——建堆 O(n) + 取 K 次 O(K log n)

Q6：建堆的时间复杂度为什么是 O(n) 而不是 O(n log n)？

直觉：n 个节点，每个最多下沉 log n 层 → O(n log n)？❌

真相：底层 n/2 个节点只下沉 0~1 层，越往上节点越少但下沉越多。

数学：∑(h=0→log n) h × n/2^(h+1) = n × ∑(h/2^(h+1)) ≈ 2n → O(n)

💡 面试时说"从最后一个非叶节点往前，每个节点下沉，总比较次数约 2n，所以是 O(n)"即可。

Q7：排序这么多，面试到底要会哪些？

必须能手写：快排（partition）、归并（merge）

必须能说清：冒泡（最简单）、插入（小数据最快）、堆排（Top-K）

必须能对比：6 种排序的时间/空间/稳定性 + Array.prototype.sort 底层

加分项：快排优化（三路、随机化、三数取中）、Top-K 问题、外部排序

图解算法与模式 · 排序算法图解 | 6 大排序 + SVG 图解 + 生活类比 + 代码对照

← 返回图解算法与模式  |  ← 返回全栈资料库首页