排序算法基础：从一次表格排序结果不稳定的问题，把冒泡、选择、插入、快排全捋一遍
排序问题最容易被低估，因为调用 Array.prototype.sort 看起来实在太顺手了。可一旦业务要求变成“先按部门排，再在部门内部按入职时间排”，真正决定结果对不对的就不只是比较函数，还有一个平时很少被认真想过的概念：稳定性。
如果一次排序不能保持相等元素原有的相对顺序，第二次排序就可能把第一次排好的分组结果打散。这个问题单看代码很难看出来，复现时却会非常诡异，看起来像 sort 有时正常、有时抽风。
后面会从这个表格排序问题切进去，把冒泡、选择、插入、快排、归并和 Array.sort 背后的稳定性与复杂度重新捋一遍。
先把问题记下来，再回头看原理
问题现场是这样的：表格数据大致是 [{dept: '技术部', joinDate: '2019-03-01'}, ...]，先按 dept 排一次：
1list.sort(function(a, b) { 2 if (a.dept < b.dept) return -1 3 if (a.dept > b.dept) return 1 4 return 0 5})
再按 joinDate 排一次：
1list.sort(function(a, b) { 2 return new Date(a.joinDate) - new Date(b.joinDate) 3})
第二次排序只看 joinDate，同一天入职的员工之间，compare 函数返回的是 0——也就是"相等，不用动"。如果排序算法是稳定的，返回 0 时元素的相对顺序会原封不动地保留下来，那么第一次按部门排好的顺序就会在第二次排序里被"带"下来，同一天入职的人还是按部门聚在一起。但如果排序不稳定，遇到"相等"时引擎完全可能把它们的相对位置打乱，因为规范没要求它非要保留原顺序。
这就是那晚我打算彻底弄明白的东西：什么是稳定排序，各种排序算法谁稳定谁不稳定，以及 2019 年的 JS 引擎里 Array.sort 到底靠不靠得住。我把这几种基础排序按"思路 — 代码 — 复杂度 — 稳不稳定"过一遍，顺序按理解的难度来，从最笨的冒泡开始。
约定一个习惯：下面所有实现都用 arr.slice() 先拷一份再排，不改入参。这是我早年吃过亏才养成的规矩——写过一个排序工具函数直接在原数组上折腾，调用方那边的数组被我就地打乱了，它后续依赖原始顺序的逻辑全错，排查了一下午才想起来是这个函数的锅。纯函数式的排序，调用方永远不用担心副作用。
冒泡排序：最笨但最直观
冒泡排序每次比较相邻元素，把大的往后冒到末尾，跑完一轮最大值就"浮"到了最后。
1function bubbleSort(arr) { 2 var list = arr.slice() 3 4 for (var i = 0; i < list.length - 1; i++) { 5 for (var j = 0; j < list.length - 1 - i; j++) { 6 if (list[j] > list[j + 1]) { 7 var temp = list[j] 8 list[j] = list[j + 1] 9 list[j + 1] = temp 10 } 11 } 12 } 13 14 return list 15}
时间复杂度是 O(n²)：外层 n 轮，内层每轮平均比较 n/2 次。它的好处只有一个——直观，谁都能看懂相邻交换这件事。
这版有个常被忽略的优化：如果某一轮一次交换都没发生，说明数组已经有序了，可以直接收工，没必要把剩下的轮次跑完。
1function bubbleSortOptimized(arr) { 2 var list = arr.slice() 3 4 for (var i = 0; i < list.length - 1; i++) { 5 var swapped = false 6 for (var j = 0; j < list.length - 1 - i; j++) { 7 if (list[j] > list[j + 1]) { 8 var temp = list[j] 9 list[j] = list[j + 1] 10 list[j + 1] = temp 11 swapped = true 12 } 13 } 14 // 一整轮没动过，数组已经有序，提前结束 15 if (!swapped) break 16 } 17 18 return list 19}
加了这个 swapped 标志后，最好情况（数组本来就有序）的复杂度从 O(n²) 降到 O(n)，只扫一遍就退出。这个细节我一开始想当然地觉得冒泡最好情况也是 O(n²)，直到自己在纸上模拟了一遍已经有序的数组才反应过来：不带这个优化，代码确实会傻乎乎地把所有轮次跑完。
冒泡是稳定排序：相等元素只在 > 时才交换，== 不动，相对顺序保得住。工程里我基本没真用过它，价值主要是把"稳定"这个概念讲清楚。
选择排序：交换少，但比较一次都省不了
每轮从未排序区间里找出最小值，和当前位置交换，把它放到前面：
1function selectionSort(arr) { 2 var list = arr.slice() 3 4 for (var i = 0; i < list.length - 1; i++) { 5 var minIndex = i 6 7 for (var j = i + 1; j < list.length; j++) { 8 if (list[j] < list[minIndex]) { 9 minIndex = j 10 } 11 } 12 13 var temp = list[i] 14 list[i] = list[minIndex] 15 list[minIndex] = temp 16 } 17 18 return list 19}
选择排序最大的特点是交换次数少：不管数组什么样，最多只交换 n-1 次（每轮一次）。比较次数则雷打不动是 O(n²)，因为它每轮都要把剩下的全扫一遍找最小值，没法像冒泡那样提前退出——哪怕数组已经有序，它也得老老实实扫完，最好情况依然是 O(n²)。
这个"交换少"的性质在某些场景有意义：如果元素"比较很便宜、但移动/交换很贵"（比如每个元素是一大块数据，搬一次成本高），选择排序的少交换反而划算。这种场景实际项目里很少碰到，知道有这么个权衡就行。
更关键的是稳定性问题，这也是我那晚重点要验证的东西：选择排序是不稳定的。举个例子，[5a, 5b, 2]（用 a/b 区分两个相等的 5），第一轮会把 2 和第一个 5a 交换，变成 [2, 5b, 5a]，两个 5 的相对顺序被打乱了。我把表格那个 bug 的场景抽象成这么个小数组在控制台里跑了一遍，看着两个"相等"的元素真的换了位置，才算把"不稳定"这个抽象词坐实成一个能摸得着的现象。
插入排序：数据基本有序时的黑马
插入排序像整理扑克牌：左手里的牌已经排好序，每摸一张新牌，就从右往左找到它该插的位置塞进去。
1function insertionSort(arr) { 2 var list = arr.slice() 3 4 for (var i = 1; i < list.length; i++) { 5 var current = list[i] 6 var j = i - 1 7 8 while (j >= 0 && list[j] > current) { 9 list[j + 1] = list[j] 10 j-- 11 } 12 13 list[j + 1] = current 14 } 15 16 return list 17}
数据基本有序时，插入排序表现非常好——内层 while 几乎一进去就退出，整体接近 O(n)。这不是纸面优势：很多语言和库的内置排序，在小数组或近乎有序的子段上会退化成插入排序，正是看中它在"小规模 + 近似有序"下常数小、又稳定的特性。V8 那套高度优化的排序实现里，对短数组也是走类似插入排序的路子，数组长到一定规模才切换到更复杂的算法，这一点我后来翻 V8 的一些资料时得到了印证。
插入排序也是稳定的：内层条件是 list[j] > current，严格大于才往后挪，相等时停下，所以相等元素不会被换到前面去。三种 O(n²) 排序里，冒泡和插入稳定、选择不稳定——这条我专门在笔记本上画了个小表格记下来，因为光背结论容易混，得知道"为什么"：冒泡和插入的交换/移动条件都是严格大于，选择排序的交换是"直接把当前位置和最小值所在位置互换"，这一下就可能跨过中间一堆相等的元素。
业务代码里我唯一真用过插入排序思路的场景，是"往一个已经有序的小数组里插入一个新元素并保持有序"——比如维护一个排行榜的 Top 10，新成绩进来时找位置插进去，比整个重排划算。
分治的第一次出场：归并排序
冒泡、选择、插入这三个 O(n²) 的算法讲完，稳定性的脾气也摸清楚了，但它们都撑不住数据量稍大的场景。真正让排序算法快起来的思路是分治，归并排序是最直接体现分治的一种：把数组从中间切开，分别排好序，再把两个有序的半段合并成一个有序整体。
1function mergeSort(arr) { 2 var list = arr.slice() 3 if (list.length <= 1) return list 4 5 var mid = Math.floor(list.length / 2) 6 var left = mergeSort(list.slice(0, mid)) 7 var right = mergeSort(list.slice(mid)) 8 9 return merge(left, right) 10} 11 12function merge(left, right) { 13 var result = [] 14 var i = 0 15 var j = 0 16 17 while (i < left.length && j < right.length) { 18 // 相等时优先取左边，这一步是稳定性的关键 19 if (left[i] <= right[j]) { 20 result.push(left[i++]) 21 } else { 22 result.push(right[j++]) 23 } 24 } 25 26 while (i < left.length) result.push(left[i++]) 27 while (j < right.length) result.push(right[j++]) 28 29 return result 30}
mergeSort 一路把数组对半切到只剩一个元素（天然有序），再由 merge 一层层合并回去，每层合并都是线性扫描，整体是 O(n log n)——切了 log n 层，每层合并总共扫 n 个元素。空间上要开辅助数组存合并结果，是 O(n)，这比原地排序费内存，但换来了稳定性和稳定的 O(n log n)，不会像下面要讲的快排那样在最坏情况下退化。
merge 函数里 left[i] <= right[j] 这一行是我那晚盯着看了很久的地方：判断条件用的是 <= 而不是 <，意味着两边相等时优先取左边那个。左边数组在原始数据里排在前面，优先取它，相等元素的相对顺序就被保住了——归并排序稳定，稳就稳在这一个符号上。反过来如果写成 <，相等时会先取右边，稳定性就没了。这行代码算是我这次笔记里印象最深的一处细节。
快速排序：面对相同问题的另一种分治
快排同样是分治，思路是选一个基准（pivot），把比它小的甩左边、比它大的甩右边，然后对左右两半递归。
1function quickSort(arr) { 2 if (arr.length <= 1) return arr 3 4 var pivot = arr[0] 5 var left = [] 6 var right = [] 7 8 for (var i = 1; i < arr.length; i++) { 9 if (arr[i] < pivot) { 10 left.push(arr[i]) 11 } else { 12 right.push(arr[i]) 13 } 14 } 15 16 return quickSort(left).concat([pivot], quickSort(right)) 17} 18 19console.log(quickSort([3, 1, 2])) // [1, 2, 3] 20console.log(quickSort([5, 3, 8, 1, 2])) // [1, 2, 3, 5, 8]
平均时间复杂度 O(n log n)，但基准选择不好时可能退化到 O(n²)。
这个版本好理解，但有两个明显问题值得深挖一层。
第一，它会创建大量新数组。每层递归都 new 出 left、right 两个数组，再 concat 拼回去，空间开销和 GC 压力都不小，不是"原地"排序。真正生产级的快排是原地分区（in-place partition），只在原数组上交换，空间复杂度降到 O(log n)（递归栈）。下面是原地版本，用经典的双指针 Lomuto 分区：
1function quickSortInPlace(arr) { 2 var list = arr.slice() 3 4 function partition(lo, hi) { 5 // 取末位做基准；实战里应随机选，见下文 6 var pivot = list[hi] 7 var i = lo - 1 8 for (var j = lo; j < hi; j++) { 9 if (list[j] < pivot) { 10 i++ 11 var t = list[i]; list[i] = list[j]; list[j] = t 12 } 13 } 14 var tmp = list[i + 1]; list[i + 1] = list[hi]; list[hi] = tmp 15 return i + 1 16 } 17 18 function sort(lo, hi) { 19 if (lo >= hi) return 20 var p = partition(lo, hi) 21 sort(lo, p - 1) 22 sort(p + 1, hi) 23 } 24 25 sort(0, list.length - 1) 26 return list 27}
第二，固定取 arr[0]（或末位）做基准会退化。如果输入本来就有序（升序或降序），每次分区都只能分出一个空的一边和一个 n-1 的一边，递归深度退化成 n，复杂度从 O(n log n) 掉到 O(n²)，还可能爆栈。我在验证这几种排序性能时特意拿一份已经排好序的数据去跑这版快排，一段平时跑得飞快的代码，遇到有序输入直接慢到卡顿，现象非常明显。
修法是随机选基准或取"头/中/尾三者的中位数"做基准，把最坏情况的概率压到极低：
1function partitionRandom(list, lo, hi) { 2 // 随机挑一个位置和末位交换，再走标准分区 3 var r = lo + Math.floor(Math.random() * (hi - lo + 1)) 4 var t = list[r]; list[r] = list[hi]; list[hi] = t 5 // ...后续同 partition 6}
还有一点，也是这次排查最相关的一点：朴素快排不稳定。分区过程中的远距离交换会打乱相等元素的相对次序，前面选择排序 [5a, 5b, 2] 那个例子在快排里同样会发生。想要稳定的 O(n log n)，就得用刚讲过的归并排序——它稳定，但要额外 O(n) 空间，这就是分治两条路线（快排 vs 归并）在稳定性上的根本分野。
回到表格：到底该不该自己实现排序
把这几种排序的稳定性摸清楚之后，我回头去查那晚表格 bug 到底是怎么回事。
ES2019 之前，规范并没有强制要求 Array.prototype.sort 必须稳定，各家引擎自行选择实现——数组长的时候走类似快排的分区思路是很常见的做法，短数组才切到插入排序这类稳定算法。V8 这两年其实已经在往稳定排序上靠，但规范没写死之前，这终究是"某个引擎当前这么实现"，不是能长期依赖的契约，其他引擎、甚至同一引擎的旧版本都可能不是这个行为。表格那个"部门顺序跟着乱跳"的现象，根子就在这——第二次按 joinDate 排序时，joinDate 相同的行谁前谁后完全没有保证，第一次按部门排好的顺序自然保不住。
ES2019 这年的规范修订把"稳定"写进了 Array.prototype.sort 的要求里，各大引擎也陆续换成了稳定的实现，但这只是"以后能指望"，不是"现在所有环境都已经这样"。团队里还有一部分用户在用旧版本浏览器，稳妥的做法是不去赌引擎实现，而是自己在比较函数里把稳定性焊死：
1// 一次比较函数里搞定多级排序，不依赖底层稳定性 2list.sort(function(a, b) { 3 return new Date(a.joinDate) - new Date(b.joinDate) || (a.dept < b.dept ? -1 : a.dept > b.dept ? 1 : 0) 4})
|| 这个写法很顺手：前一个维度比出胜负（非 0）就用它，否则落到下一个维度。把多级排序合并进一个比较函数里一次排完，而不是先排一次部门、再排一次时间指望它"顺带"保留，这样无论底层排序稳不稳定，结果都是确定的。我把这个改法提交之后又拉着几个同样场景的报表页面回归了一遍，"排完更乱"的反馈没再出现过。
这件事也让我对"什么时候该自己实现排序"这个问题有了更实际的判断：业务里绝大多数排序场景，直接用 Array.sort 就够了，几百上千条数据，引擎内置实现比自己手写的任何版本都快、都稳。真正需要自己动手的场景其实很窄——要么是需要精确控制稳定性且不想依赖引擎版本（就像这次），要么是要在受限环境里（比如禁止用某些内置 API 的沙箱、或者需要可中断的排序过程）自己控制排序的执行方式。数据量大到内置排序都扛不住时，第一反应也不该是自己写个更快的排序，而是这排序该不该挪到后端、挪到数据库的 ORDER BY——前端排几万条数据本身就是个信号，说明数据该分页或该在服务端处理了。
sort 要传比较函数
排查这次 bug 的过程里，我还把 sort 的默认行为重新过了一遍，顺手记下几个坑。JavaScript 默认排序会把元素转成字符串再按 UTF-16 码点比较，不传比较函数时数字会被坑：
1[10, 1, 2].sort() // [1, 10, 2] ← '10' < '2' 因为先比 '1' 和 '2' 2[10, 1, 2].sort((a, b) => a - b) // [1, 2, 10] ← 这才是数字升序
[1, 10, 2] 这个结果第一次见会很懵：'10' 排在 '2' 前面，是因为字符串比较从首字符起，'1' 的码点小于 '2'，根本轮不到看第二位。数字排序必须显式传比较函数，返回负数表示 a 排前面，正数表示 b 排前面，0 表示不变。记住 a - b 是升序、b - a 是降序就行。
还有几个相关的坑我也栽过：
比较函数返回布尔值是错的。见过有人写 (a, b) => a > b，返回 true/false，而 sort 期待的是数字。true 被当成 1、false 当成 0，永远不会返回负数，结果在不同引擎下行为不一致，排出来的顺序莫名其妙。一定要返回数字差。
大整数相减会溢出/精度问题。如果是时间戳这种大数，a - b 一般没事；但要排的是可能超出安全整数范围的值，稳妥写法是 (a, b) => a < b ? -1 : a > b ? 1 : 0。
对象数组按字段排序，封装一个小工具很省心：
1function sortBy(arr, key) { 2 return arr.slice().sort(function(a, b) { 3 return a[key] - b[key] 4 }) 5} 6sortBy(users, 'age')
字符串字段要本地化排序（中文、带音标的字母），别直接用 >，用 a.localeCompare(b)，否则中文会按 Unicode 码点排，得到一堆没人看得懂的顺序。类目、部门这类中文字段排序，我这次顺手也检查了一遍，还好之前都规规矩矩用了 localeCompare。
复杂度速查
把这几种排序过完一遍之后，我把结论整理成一张表贴在笔记本里，省得下次又要现推：
1算法 平均 最坏 最好 空间 稳定 2冒泡 O(n²) O(n²) O(n)* O(1) 稳定 3选择 O(n²) O(n²) O(n²) O(1) 不稳定 4插入 O(n²) O(n²) O(n) O(1) 稳定 5快排 O(n log n) O(n²) O(n log n) O(log n) 不稳定 6归并 O(n log n) O(n log n) O(n log n) O(n) 稳定
* 冒泡的 O(n) 最好情况需要带"提前退出"优化。
对这张表我没打算死背，而是记每一格背后的原因：选择排序最好情况也是 O(n²)，因为它每轮必须扫完才知道最小值；归并空间是 O(n)，因为合并要开辅助数组；快排不稳定，因为分区有远距离交换；归并稳定，因为合并时相等优先取左边。能把"为什么"讲出来，比记住表格里的符号管用得多。
冒泡、选择、插入是 O(n²) 的基础三件套，理解它们主要是为了建立对复杂度和稳定性的直觉；快排和归并才是 O(n log n) 这一档，也是分治思想真正的体现——两者复杂度相当，差别全在稳定性和空间上，选哪个取决于业务到底在不在乎"相等元素的顺序"。
那次表格排序的问题，最后的教训被我写进了团队的排序小抄里：多字段排序永远合并进一个比较函数一次排完，不要指望连续调用两次 sort 靠底层稳定性去"续"上一次的顺序。这条不占篇幅，但下次再有人写出"先排 A 再排 B"这种代码，我能一眼看出问题在哪，而不用再等用户在群里报一次 bug。