Array.prototype.sort 是数组提供的排序方法，如其名，是数组排序的函数。

# 第一次见面 ↵

去年刚刚学习前端的时候就知道有这个方法了，那时候我觉得很神奇，sort 可以接受一个函数作为参数，那时候我不知道有函数式编程这种编程范式存在，但是我确实是感受到了函数作为一等公民带来的灵活性。

# 使用 ↵

使用很简单直接对数组调用 sort 就可以了，可以传递判断函数让 sort 来比对元素之间的关系：

00var a = [5, 4, 3, 2, 1]; 
01a.sort((a, b) => a - b); 
02
03console.log(a); 
04// => [1, 2, 3, 4 ,5]

可以看到使用 sort 的时候可以指定一个 比较函数 用于判断元素之间的关系。

当传递了比较函数给 sort 的时候：

如果比较函数的返回值小于 0 ，那么 a 会被排列到 b 之前；
如果比较函数的返回值等于 0 ， a 和 b 的相对位置不变。备注： ECMAScript 标准并不保证这一行为，而且也不是所有浏览器都会遵守（例如 Mozilla 在 2003 年之前的版本）；
如果比较函数的返回值大于 0 ， b 会被排列到 a 之前。
而且比较函数的返回值必须总是对相同的输入返回相同的比较结果，否则排序的结果将是不确定的。

上述 4 点摘抄自 MDN - Array.prototype.sort

总的来说就是：

比较函数是纯函数，输入确定了，输出唯一确定。

比较函数有两个参数，习惯的命名是左边的是 a，右边的是 b
且如果把函数当成某种运算 @，则上述 1 和 3 可以统一成：

a @ b < 0 ===> [a, b]
a @ b > 0 ===> [b, a]

# 其他需要注意的地方 ↵

sort 方法会改变原数组，这是它面向对象的特性

00var a = [3, 2, 1, 0]; 
01a.sort((a, b) => a - b); 
02
03console.log(a);

会打印出 0, 1, 2, 3 原数组被永久的改变了。

如果不指定排序的第一个参数：判断函数的话，则按照字典序来排序这是一个大坑

00var a = [20, 18, 17, 12, 10, 9, 5, 4, 2, 1, 0, -12]; 
01a.sort();
02
03console.log(a); 
04// => [-12, 0, 1, 10, 12, 17, 18, 2, 20, 4, 5, 9]

答案会是 [-12, 0, 1, 10, 12, 17, 18, 2, 20, 4, 5, 9] 这种按照字典序的排序，因此如果要严格的实数排序，要传入比较函数。

# 性能 ↵

作为浏览器提供的排序方法，性能还是很不错的。（我也做过测试，比我自己用递归实现的快排快很多）

在 V8 上，sort 排序是看数组长度来确定排序算法的。

长度小于 10 的数组用简单的 插入排序，大于 10 就用性能更好的 快速排序

详见 Github 上 V8 源码

00  // In-place QuickSort algorithm.
01  // For short (length <= 10) arrays, insertion sort is used for efficiency.

在 710 行有上面这一段话。

# 递归实现一个快排 ↵

00// 柯里化 
01// 从 arr 里面 挑选出比 val 大的元素并构成新数组
02var gt = arr => val => arr.reduce((acc, cur) => {
03    if (cur > val) acc.push(cur); 
04    return acc; 
05}, []); 
06
07// 柯里化
08// 从 arr 里面 挑选出比 val 小的元素并构成新数组
09var lt = arr => val => arr.reduce((acc, cur) => {
10    if (cur < val) acc.push(cur); 
11    return acc; 
12}, []); 
13
14// 正体 
15var qs = arr => {
16    if (arr.length === 1 || arr.length === 0) return arr; 
17
18    let temp = arr[0]
19        , sub = arr.slice(1)
20        , gtArr = qs(
21            gt(sub)(temp)
22        )
23        , ltArr = qs(
24            lt(sub)(temp)
25        ); 
26
27    // return ltArr ++ [temp] ++ gtArr 
28    return ltArr.concat([temp]).concat(gtArr); 
29}

每次筛选出比第一个元素要小的数组集、和比他大的数组集，然后拼接。

# Links ↵

array.js - Github 上 V8 实现array的源码
MDN - Array.prototype.sort