← 返回手写题目录

⚡ 排序算法手写 Top 8

冒泡 · 选择 · 插入 · 快排 · 归并 · 计数 · 堆排 · 复杂度对比

复杂度总览冒泡选择插入快排归并计数堆排sort原理

📊 复杂度对比总览（必背）

算法平均时间最坏时间空间稳定性面试频率
冒泡排序O(n²)O(n²)O(1)稳定★★★ 必背
选择排序O(n²)O(n²)O(1)不稳定★★ 了解
插入排序O(n²)O(n²)O(1)稳定★★★ 必背
快速排序O(n log n)O(n²)O(log n)不稳定★★★★★ 必考
归并排序O(n log n)O(n log n)O(n)稳定★★★★ 高频
堆排序O(n log n)O(n log n)O(1)不稳定★★★ 高频
计数排序O(n+k)O(n+k)O(k)稳定★★ 进阶
希尔排序O(n log² n)O(n²)O(1)不稳定★ 了解
稳定性含义：相同元素的相对顺序排序后不变。例如 [{age:18,name:'A'},{age:18,name:'B'}] 按 age 排序，稳定排序保证 A 还在 B 前面。面试常考。
记忆口诀：
① "插冒归计" 稳定（插入/冒泡/归并/计数）
② "快选堆希" 不稳定（快排/选择/堆排/希尔）
③ n² 算法：插冒选（小数据量简单）
④ n log n 算法：快归堆（大数据量主力）

O(n²) 基础算法（必背）

1冒泡排序（相邻比较交换）

思路：相邻两个元素比较，大的往后挪，每轮把最大的"冒泡"到末尾。像水底气泡上浮。

function bubbleSort(arr) { const a = [...arr] // 不修改原数组 for (let i = 0; i < a.length - 1; i++) { let swapped = false // 优化：本轮没交换说明已有序 for (let j = 0; j < a.length - 1 - i; j++) { if (a[j] > a[j + 1]) { [a[j], a[j + 1]] = [a[j + 1, a[j]]] // 交换 swapped = true } } if (!swapped) break // 没交换 → 已有序，提前退出 } return a } bubbleSort([5, 3, 8, 1, 2]) // [1,2,3,5,8] // 过程演示（5,3,8,1,2）： // 第1轮：[3,5,1,2,8] 8 冒到最后 // 第2轮：[3,1,2,5,8] 5 冒到倒数第二 // 第3轮：[1,2,3,5,8] 3 到位 // 第4轮：无交换 → break
关键：内层循环长度 a.length - 1 - i，因为末尾 i 个已经排好。swapped 优化能让最好情况变 O(n)。
2选择排序（每轮找最小放前面）

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

function selectionSort(arr) { const a = [...arr] for (let i = 0; i < a.length - 1; i++) { let minIndex = i // 在 [i, end) 找最小值的索引 for (let j = i + 1; j < a.length; j++) { if (a[j] < a[minIndex]) minIndex = j } // 把最小值交换到位置 i if (minIndex !== i) { [a[i], a[minIndex]] = [a[minIndex], a[i]] } } return a } selectionSort([5, 3, 8, 1, 2]) // [1,2,3,5,8] // 过程：[5,3,8,1,2] // i=0: 最小是1（索引3）→ 交换 → [1,3,8,5,2] // i=1: 最小是2（索引4）→ 交换 → [1,2,8,5,3] // i=2: 最小是3（索引4）→ 交换 → [1,2,3,5,8] // i=3: 最小是5（索引3）→ 不变 → [1,2,3,5,8]
特点：交换次数最少（最多 n-1 次），但比较次数固定 O(n²)。不稳定——例如 [5,5,2] 排序后两个 5 的顺序会变。
3插入排序（扑克牌思路）

思路：像整理扑克牌，把新牌插入到已排序的合适位置。对小数据或近乎有序的数组最快。

function insertionSort(arr) { const a = [...arr] for (let i = 1; i < a.length; i++) { const current = a[i] // 待插入的牌 let j = i - 1 // 比 current 大的都往后挪一位 while (j >= 0 && a[j] > current) { a[j + 1] = a[j] j-- } a[j + 1] = current // 插入到正确位置 } return a } insertionSort([5, 3, 8, 1, 2]) // [1,2,3,5,8] // 过程（[] 表示已排序区）： // [5] 3 8 1 2 → [3,5] 8 1 2 // [3,5] 8 1 2 → [3,5,8] 1 2 // [3,5,8] 1 2 → [1,3,5,8] 2 // [1,3,5,8] 2 → [1,2,3,5,8]
优势：① 近乎有序数据 O(n)；② 在线算法（边来边插）；③ 是希尔排序的基础。Chrome 的 Array.sort 在小数组（<10）时就用插入排序。

O(n log n) 高效算法（必考）

4快速排序（分治 + 基准元素）★★★★★

思路：选一个基准（pivot），比它小的放左、大的放右，递归排左右两部分。面试必考 TOP1。

// 版本1：简洁版（易懂，但空间 O(n)） function quickSort(arr) { if (arr.length <= 1) return arr const pivot = arr[0] // 选第一个作基准 const left = [], right = [] for (let i = 1; i < arr.length; i++) { if (arr[i] < pivot) left.push(arr[i]) else right.push(arr[i]) } return [...quickSort(left), pivot, ...quickSort(right)] } quickSort([5, 3, 8, 1, 2, 7]) // [3,1,2] 5 [8,7] → [1,2,3] 5 [7,8] → [1,2,3,5,7,8] // 版本2：原地版（in-place，空间 O(log n)，面试加分） function quickSortInPlace(arr, low = 0, high = arr.length - 1) { if (low < high) { const pivotIndex = partition(arr, low, high) quickSortInPlace(arr, low, pivotIndex - 1) quickSortInPlace(arr, pivotIndex + 1, high) } return arr } function partition(arr, low, high) { const pivot = arr[high] // 取最后一个作基准 let i = low - 1 // i 指向"小于区"的末尾 for (let j = low; j < high; j++) { if (arr[j] < pivot) { i++ [arr[i], arr[j]] = [arr[j], arr[i]] } } [arr[i + 1], arr[high]] = [arr[high], arr[i + 1]] // 基准归位 return i + 1 }
面试建议：先写版本1（思路清晰），面试官追问"能不能原地"再写版本2。提到三数取中（优化最坏情况）能加分。
最坏情况：数组已有序且每次取首/尾作基准，退化为 O(n²)。解决方法：随机选基准 / 三数取中。
5归并排序（分治 + 合并）★★★★

思路：先拆成单元素（有序），再两两合并成有序数组。稳定排序，链表排序首选。

function mergeSort(arr) { if (arr.length <= 1) return arr // ① 分：从中间切成两半 const mid = Math.floor(arr.length / 2) const left = mergeSort(arr.slice(0, mid)) const right = mergeSort(arr.slice(mid)) // ② 治：合并两个有序数组 return merge(left, right) } function merge(left, right) { const result = [] let i = 0, j = 0 // 双指针，谁小谁先进结果 while (i < left.length && j < right.length) { if (left[i] <= right[j]) result.push(left[i++]) else result.push(right[j++]) } // 把剩余的拼上 return result.concat(left.slice(i)).concat(right.slice(j)) } mergeSort([5, 3, 8, 1, 2, 7]) // [5,3,8] [1,2,7] // → [5] [3,8] → [3,5,8] [1] [2,7] → [1,2,7] // → merge([3,5,8], [1,2,7]) → [1,2,3,5,7,8]
核心：merge 函数合并两个有序数组，是归并、外排序的基础。注意 left[i] <= right[j] 保证稳定性（相等时取左边）。
对比快排：归并稳定、最坏也是 O(n log n)，但空间 O(n)；快排平均更快、空间小，但不稳定、最坏 O(n²)。
6计数排序（非比较，O(n+k)）

思路：用数组下标表示值，统计每个值出现次数。仅适用于值范围不大的整数。

function countingSort(arr) { if (arr.length === 0) return arr // ① 找最大最小值确定范围 const max = Math.max(...arr) const min = Math.min(...arr) const range = max - min + 1 // ② 统计每个值出现次数（下标 = 值 - min） const count = new Array(range).fill(0) arr.forEach(v => count[v - min]++) // ③ 按计数还原排序结果 const result = [] count.forEach((c, i) => { for (let k = 0; k < c; k++) { result.push(i + min) } }) return result } countingSort([4, 2, 2, 8, 3, 3, 1]) // [1,2,2,3,3,4,8] // 适用：年龄排序（0-150）、分数排序（0-100）等值域小的整数 // 不适用：浮点数、值域过大（如 1 和 1000000）
价值：突破比较排序的 O(n log n) 下限，达到 O(n)。是基数排序、桶排序的基础。面试提一句能加分。
7堆排序（建堆 + 调整）★★★

思路：先建成大顶堆，再把堆顶（最大值）和末尾交换，缩小堆，重新调整。原地排序，空间 O(1)。

function heapSort(arr) { const a = [...arr] const n = a.length // ① 建大顶堆：从最后一个非叶子节点开始向上调整 for (let i = Math.floor(n / 2) - 1; i >= 0; i--) { heapify(a, n, i) } // ② 逐个把堆顶（最大）换到末尾，缩小堆再调整 for (let i = n - 1; i > 0; i--) { [a[0], a[i]] = [a[i], a[0]] // 堆顶（最大）换到末尾 heapify(a, i, 0) // 对剩余 i 个元素重新建堆 } return a } // 调整以 i 为根的子树为大顶堆 function heapify(arr, n, i) { let largest = i const left = 2 * i + 1 // 左孩子索引 const right = 2 * i + 2 // 右孩子索引 if (left < n && arr[left] > arr[largest]) largest = left if (right < n && arr[right] > arr[largest]) largest = right if (largest !== i) { [arr[i], arr[largest]] = [arr[largest], arr[i]] heapify(arr, n, largest) // 递归调整被交换的子树 } } heapSort([5, 3, 8, 1, 2, 7]) // [1,2,3,5,7,8] // 堆的数组表示： // 父节点 i 的左孩子 = 2i+1，右孩子 = 2i+2 // 孩子的父节点 = Math.floor((i-1)/2)
价值：① 原地排序，空间 O(1)；② 最坏也是 O(n log n)；③ Top K 问题首选（小顶堆维护 K 个最大）。面试常考 Top K。

扩展知识

8Array.sort 的底层原理（V8 实现）

面试追问："你说的排序我都懂，那 Array.sort 底层用什么算法？"——能答出这个就是高级前端。

// V8 引擎的 sort 实现（Chrome / Node.js）： // - 当数组长度 > 10：用 TimSort（归并 + 插入的混合算法） // - 当数组长度 ≤ 10：用插入排序（小数组更快） // TimSort 也是 Python、Java 的默认排序 // 注意：默认按字符串 Unicode 排序！ [10, 2, 1, 21].sort() // [1, 10, 2, 21] —— 字符串排序，不是数字排序！ // 必须传比较函数 [10, 2, 1, 21].sort((a, b) => a - b) // [1, 2, 10, 21] // 比较函数规则： // 返回 < 0：a 排前面 // 返回 > 0：b 排前面 // 返回 = 0：顺序不变 // 对象数组按字段排序 users.sort((a, b) => a.age - b.age) // 按 age 升序 users.sort((a, b) => b.createTime - a.createTime) // 按时间降序 // 中文字符串排序（按拼音） ['张三', '李四', '王五'].sort(new Intl.Collator('zh-CN').compare)
TimSort 优势：① 对部分有序数据特别快（接近 O(n)）；② 稳定排序；③ 实际性能比纯快排还好。是工业级排序的首选。
面试加分：能说出 "V8 用 TimSort，小数组退化为插入排序" 就超过 90% 候选人。再补充 TimSort 是归并+插入的混合，稳定排序，更是满分。
★Top K 问题（堆的经典应用）

场景：找出 100 万数据中最大的 10 个。用小顶堆维护 K 个元素，比全排序快得多。

// 找最大的 K 个：维护大小为 K 的小顶堆 // 新元素比堆顶大 → 替换堆顶并下沉调整 function topK(arr, k) { const heap = arr.slice(0, k).sort((a, b) => a - b) // 初始小顶堆 for (let i = k; i < arr.length; i++) { if (arr[i] > heap[0]) { // 比堆顶大才入堆 heap[0] = arr[i] heap.sort((a, b) => a - b) // 重新排序（简化版，生产用下沉操作 O(log k)） } } return heap } topK([3, 1, 5, 7, 2, 8, 6, 4], 3) // [6, 7, 8] 最大的3个 // 复杂度：O(n log k)，比排序 O(n log n) 快 // 当 k << n 时优势明显（如 100万找 top 10）
关键：找最大的 K 个用小顶堆（堆顶是 K 个里最小的，方便淘汰）；找最小的 K 个用大顶堆。别搞反了。
🎯 排序复习重点（按面试频率）：
① 快排（必考）：能默写，会写原地版
② 归并（高频）：稳定排序，merge 函数要熟
③ 冒泡/插入（必背）：基础题，要会写优化版
④ 堆排（高频）：能写出 heapify，会做 Top K
⑤ 复杂度表：平均/最坏时间、空间、稳定性全背下来
⑥ Array.sort 原理：能说出 TimSort 是高级表现
排序算法手写 · 面试突击 · 全栈资料库