JavaScript sort() 方法你真的了解吗？

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 编码中，「数字 < 大写字母 < 小写字母 < 汉字」。因此，在开头那个栗子中：

1. 首先先将每个元素转为字符串：['3', '15', '8', '29', '102', '22']
2. 紧接着 sort 会从左到右对比每个字符串
3. 根据第一个字符排序得到：['15', '102', '29', '22', '3', '8']
4. 然后根据第二个字符排序得到：['102', '15', '22', '29', '3', '8']
5. 最后得到结果：['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 个元素挑出一个元素，放到一个新数组中，然后对它排序，找到中间位置的数，以此作为中位数。