MinimalistYing.io

Array.prototype.sort() 在使用默认 CompareFn 时的问题
2018-09-29
技术
Javascript

起因

在 LeetCode 上碰到一道算法题,需要先将数组中的数字从小到大进行排序。

自信的直接通过 Array.prototype.sort() 进行排序,结果却让人费解:

let arr = [1, -2, 2, 34, 3]
arr.sort() // => [-2, 1, 2, 3, 34]
// 暂时来看默认的排序算法是正确的 下面我们换一下数组内部的值
arr = [1, -1, 23, 2, 3]
arr.sort() // => [-1, 1, 2, 23, 3]
// 可以看到结果并未正确的按从小到大的顺序排列

Why

查阅 ECMA 规范中的 sortcompare

默认的比较函数会将数组中的值(除了undefined,因为它不能被转为字符串)先转为字符串后再进行排序,并且undefined会被视为最大的值,所以:

let arr = [1, undefined, 23, 2, 3]
// 因为 '3' > '23' > '2' > '1' 
arr.sort() // => [1, 2, 23, 3, undefined]

延伸

查找相关资料的时候翻到了这篇文章,里面又抛出了一个新问题:

const data = [
    {value: 3}, 
    {value: 2}, 
    {value: undefined}, 
    {value: 1}, 
    {value: undefined}, 
    {value: 4}
]
// => [1, 2, 3, 4, undefined, undefined]
data.map(x => x.value).sort((x, y) => x - y)
// => [2, 3, undefined, 1, undefined, 4]
data.sort((x, y) => x.value - y.value).map(x => x.value)

可以看到先排序再扁平化和先扁平化再排序产出的结果是不一致的,虽然比较大小的逻辑相同。

产生这个问题的原因就是因为值中出现了undefined而它和任何其它数字进行加减乘除操作得到的结果是NaN,而 ECMA 规范中规定的 CompareFn 必须返回的是一个数字(最好是1,-1,0)。对于给定的compare(a,b)希望 a 排前返回负数,希望 b 排前返回正数,希望顺序不变返回 0。

总结

为了避免诸多问题,建议在使用 Array.prototype.sort() 时始终传入 CompareFn,并考虑清楚对比值中可能出现的特殊情况(例如undefined/null等)。