JavaScript sort() 方法你真的了解吗？
有一次，我在刷 LeetCode 的时候，明明觉得没有问题，然而最后还是答案错误。经过调试发现原来问题出现在 sort() 这个数组方法。sort 作为一个很常见的数组方法，却是数组方法中最复杂的方法之一。我们直接看下面代码：
const arr = [3, 15, 8, 29, 102, 22]; arr.sort(); console.log(arr);
相信很多人会这么想：这不就是对数组排序嘛，没指定规则，一般默认升序，所以输出结果为：[3, 8, 15, 22, 29, 102]。然而结果却出乎意料：[102, 15, 22, 29, 3, 8]。这又是为什么呢？看完后面的内容，相信你会明白这其中的原理了。
1. sort 的定义
sort() 方法对数组的元素进行排序，并返回数组。默认排序顺序是在「将元素转换为字符串」，然后比较它们的 UTF-16 代码单元值序列时构建的。
我们知道 unicode 编码中，「数字 < 大写字母 < 小写字母 < 汉字」。因此，在开头那个栗子中：
- 首先先将每个元素转为字符串：
['3', '15', '8', '29', '102', '22'] - 紧接着
sort会从左到右对比每个字符串 - 根据第一个字符排序得到：
['15', '102', '29', '22', '3', '8'] - 然后根据第二个字符排序得到：
['102', '15', '22', '29', '3', '8'] - 最后得到结果：
['102', '15', '22', '29', '3', '8']
现在应该明白为什么会出现这种结果了吧。那么问题来了，如果我们想要实现数字的升序排序或者降序排序，那该怎么办呢？这个时候我们得先了解一下它的用法。
2. sort 的用法
arr.sort([compareFunction])
可以看到 sort 方法是可以传递一个参数 compareFunction，该参数用来指定按某种顺序进行排列的函数。如果省略，元素按照转换为的字符串的各个字符的 Unicode 位点进行排序。
如果指明了 compareFunction，那么数组会按照调用该函数的返回值排序。即 a 和 b 是两个将要被比较的元素：
- 如果
compareFunction(a, b)小于0，那么a会被排列到b之前； - 如果
compareFunction(a, b)等于0，a和b的相对位置不变。 - 如果
compareFunction(a, b)大于0，b会被排列到a之前。 compareFunction(a, b)必须总是对相同的输入返回相同的比较结果，否则排序的结果将是不确定的。
因此要比较数字而非字符串，比较函数可以简单的以 a 减 b，如下的函数将会将数组升序排列：
function compareNumbers(a, b) { return a - b; }
sort 方法可以使用函数表达式方便地书写：
var numbers = [4, 2, 5, 1, 3]; numbers.sort(function(a, b) { return a - b; }); console.log(numbers); // 也可以写成： var numbers = [4, 2, 5, 1, 3]; numbers.sort((a, b) => a - b); console.log(numbers); // [1, 2, 3, 4, 5]
3. sort 的原理
或许读者会好奇，sort 底层讲究是如何实现排序的？
查阅 v8源码sort部分 我们可以发现，对于需要排序的元素个数 n，具体排序策略有几下中情形：
- 当 n<=10 时，采用插入排序；
- 当 n >10 时，采用三路快速排序；
- 10 < n <= 1000，采用中位数作为哨兵元素；
- n > 1000，每隔 200~215 个元素挑出一个元素，放到一个新数组中，然后对它排序，找到中间位置的数，以此作为中位数。
