JavaScript – Sort

前言

排序是很常见的需求. 虽然看似简单, 但其实暗藏杀机. 一不小心就会搞出 Bug 哦.

这篇就来聊聊 JS 的排序.

参考

原生JS数组sort()排序方法内部原理探究

值的比较 

js中的localeCompare到底是如何比较的？

直觉和特殊场景

说到排序. 一般人熟悉的情况是这些

直观的

英文 a 到 z 顺序

中文 阿, 八, 差, 依据汉语拼音的英文字母顺序

数字 -1 < 0 < 1 negative < zero < positive 小到大

日期 01-01-2023, 02-01-2023, 03-01-2023 过去到未来

这些都很直观, 但是真实情况却往往会有超出我们的预料, 比如

特殊的

a 和 A 字母大小写区别. 先 a 还是先 A?

null or undefined or empty string or NaN 排前面还是后面? 

不同类型对比是怎样, 100 > 'abc'?

符号对比, '~' > '@' 谁先谁后?

老实说这种奇葩场景就不应该存在. 因为它们就是来乱的丫.

String Comparison

两个字符串比大小 (e.g. 'abc', 'xyz')

首先各自取出第一个字符 (e.g. 'a' vs 'x')

然后转换成 Unicode

'a'.charCodeAt(0); // 97
'x'.charCodeAt(0); // 120

然后比大小. 97 小于 120, 所以 "顺序" 的情况下, 字符 'a' 在 字符 'z' 的前面

结论: 对于字符串, 它是一个一个逐个转换成 Unicode 比较得出结果的 (如果第一个字符相同, 那就继续比第二个. 直到不相同来分胜负)

另外, empty string 的 Unicode 是 0 所以 empty string 总是在前面.

['a', ''].sort(); // ['', 'a'] empty Unicode 0 所以前面
['abc', 'abcd'].sort(); // 前面 3 个字符相同, 第 4 个是 emtpty string vs 'd' 也就是 0 vs 100 所以 abc 胜

以上逻辑也适用于 C#

Number Comparison

-1 < 0 < 1

negative < zero < positive

这个很好理解. 但是 JS 中有一个奇葩叫 NaN

它是一个数字又不是一个数字. 它的特色是无论和什么数字比大小结果都是 false

NaN > 0; // false 
NaN < 0; // false
NaN > 1; // false
NaN < 1; // false

它不比任何数字大, 也不比任何数字小 ....

JS comparison auto convert type

a > b 当 a,b 类型不相同时, JS 会把它们都转换成 Number 来对比. 以前在 JavaScript – 类型转换 也有提到过.

当然还是建议不要让它自动转换的好.

Array.sort 默认行为

好, 我们已经有一点基础了. 来看看 JS 的 Array.sort 是如何排序的吧. 

我们不注重它使用了什么排序方式 (插排, 快排, 冒泡排). 我们只关心它排序的结果.

['z', 'b', 'a'].sort(); // ["a", "b", "z"]
['差' , '八', '阿'].sort(); // ["八", "差", "阿"]
[1, 11, 2, 3].sort(); // [1, 11, 2, 3]
[null, undefined, 'm', 'o', 't', 'v'].sort(); // ["m", null, "o", "t", "v", undefined]
[new Date('2023-01-01'), new Date('2023-01-02'), new Date('2023-01-04')].sort(); // [2号, 1号, 4号]

第一个正常

第二个...汉字并没有依据汉语拼音排序

第三个... 11 比 2,3 小? 

第四个... null 在 m 和 o 中间? undefined 在最后? 

第五个... 2号比1号早 ?

真的是奇葩到...不能用丫.

Array.sort 默认的行为是这样的. 首先把所有的值强转成 string, 然后进行 string comparison.

第二题的中文字, 因为 string comparison 是比 Unicode 的号码, 而不是依据汉语拼音, 所以顺序就不对了.

['差' , '八', '阿'].map(v => v.charCodeAt(0)); // [24046, 20843, 38463]

转成 Unicode 比较后顺序是 20843 差, 24046 八, 38463 阿. 

第三题 11 被转换成了 string '11',  string comparison 是逐个字母对比的, 于是 

'11' vs '2' = '1' vs '2' = Unicode 49 vs 50. 结果 '11' 获胜

第四题 null 被强转 string 的结果是 'null' 而 undefined 强转 string 的结果 'undefined'

于是 string comparison 结果 'm', 'null', 'o' 就可以理解了. 但是 undefined 理应在 't', 'undefined', 'v' 丫. 但却在最后.

这是因为它是一个特殊对待 Stack Overflow – javascript array.sort with undefined values, undefined 总是排在最后面.

第五题 日期被强转成 string 后变成 

1号 = Sun Jan 01 2023 08:00:00 GMT+0800 (Malaysia Time)

2号 = Mon..

4号 = Wed...

于是 string comparison 的顺序是 Mon, Sun, Wed = 2号, 1号, 4号

自定义 Array.sort

Array.sort 默认行为很难用于真实的开发场景. 所以我们需要自定义. 它允许我们提供一个 comparison 方法.

[1, 11, 2, 3].sort((a, b) => a - b); // [1, 2, 3, 11] 

这样就正常了.

它的工作原理是这样的

a 和 b 是 2 个 array 中的值, 我们不需要理会这 2 个的出现顺序和次数. 这些会依据 JS 使用的排序方法而定.

我们只关心这 2 个值对比后哪一个胜出就可以了

当获取到 a = 2, b = 11 时.

如果我们想表达 a 小于 b 那么方法就返回 negative, 想表达 a 大于 b 就返回 positive, 想表达 2 个值相等就返回 0

接着 JS 就会处理后续的事儿了.

所以看回上面的代码 return a - b

当 a = 2, b = 11

a - b = -9 negative 表示 a 小于 b

至此我们就可以完全掌控要如何排序了

1. 数字排序

[1, 11, 2].sort(); // [1, 11, 2] 
[1, 11, 2].sort((a, b) => a - b); // [1, 2, 11]

2. 大小写排序

console.log(['a', 'A', 'b', 'B'].sort()); // ["A", "B", "a", "b"] 
console.log(['a', 'A', 'b', 'B'].sort((a, b) => a.localeCompare(b))); // ["a", "A", "b", "B"] 

sort 默认是依据 Unicode 排序, 那么大写字母肯定都在小写字母前面. 如果不希望这样的话, 可以改用 localeCompare

这个 localeCompare 的排序方式比较人性化. 它是小写在前面, 而且 A 也小于 b. C# LINQ 应该也是这样的. SQL Server 则默认是不区分大小写的 

3. 中文排序

['差' , '八', '阿'].sort(); // ["八", "差", "阿"] 
['差' , '八', '阿'].sort((a, b) => a.localeCompare(b, 'zh-CN')); // ["阿", "八", "差"]

同样是用了 localeCompare 方法, 通过 'zh-CN' 表达是简体汉字, 于是它就变成了用汉语拼音排序. 确实挺人性化的.

这个 locale 的标准是 BCP 47, 所以通常是用 en-US 和 zh-CN (简体中文) / zh-TW (繁体中文)

题外话, 要判断字符串是不是汉字其实挺难的. 

参考: 

Stack Overflow – What's the complete range for Chinese characters in Unicode?

Stack Overflow – Is there a way to check whether unicode text is in a certain language? (C#)

思路大概是这样 (注: 如果你对 Unicode, 十进制, 十六进制不熟悉, 先看这篇 Bit, Byte, ASCII, Unicode, UTF, Base64)

首先我们要知道汉字的 Unicode range. 这个超级多的, 但凡有 CJK 开头的都可以算是汉字, 但是汉字不只是中国的, 日本韩国也参进去了. 有些汉字只有日本有, 这些都比较乱水.

我拿最 common 的来举例

4E00 – 9FFF 是其中一个 range. 它使用十六进制来表达.

先把它换成十进制, 这样比较容易处理

const chineseRangeFrom = '4E00';
const chineseRangeTo = '9FFF';

// 把 十六进制 转成 十进制
const from = parseInt(chineseRangeFrom, 16); // 19968 
const to = parseInt(chineseRangeTo, 16); // 40959

假设我们有一个汉字 "严"

const value = '严';
// convert to Unicode (十进制)
const unicode = value.charCodeAt(0); // 20005 这个是十进制

我们通过 charCodeAt 找出它的 Unicode 号. 这个返回的是十进制哦.

最后我们可以判断这个号是否在 range 里面. 在 range 里面的就表示它是汉字.

if(unicode >= from && unicode <= to) {
    console.log('yes is chinese char');
}

题外话, C# 是通过 set global culture 来实现的...非常友好!

Thread.CurrentThread.CurrentCulture = new System.Globalization.CultureInfo("zh-Hans");
var values = new string[] { "差", "阿", "八" };
var newValues = values.Order(); // ["阿", "八", "差"]

5. null 的排序

SQL Server 和 C# LINQ order by 都是把 null 放前面 (顺序), 但不是所以 Database 都这样哦. JS 则完全我们自己决定.

console.log(['m', 'o', null].sort()); // ["m", null, "o"] 

console.log(['m', 'o', null].sort((a, b) => {
    if(a === null && b === null) return 0
    if(a === null) return -1; // 想 null 在后面这里就返回 1
    if(b === null) return 1;  // 想 null 在后面这里就返回 -1
    return a.localeCompare(b);
})); // [null, "m", "o"] 

5. 日期排序

console.log([
    new Date('2023-01-01'), 
    new Date('2023-01-02'), 
    new Date('2023-01-04')
].sort()); // 2号， 1号， 4号

console.log([
    new Date('2023-01-01'), 
    new Date('2023-01-02'), 
    new Date('2023-01-04')
].sort((a, b) => a.getTime() - b.getTime())); // 1号, 2号, 4号

这里需要注意一点, 如果出现 invalid date 该怎么处理呢? 放任它不管的话, invalid date getTime 会得到 NaN

而 sort 函数理应返回 negative, zero, positive. 当返回 NaN 时, 它的效果相等于返回 zero.

切记排序时要想清楚所有可能出现的 value, 并且明确表面它们的顺序.

还有一个无敌 modern 的方式是用 Temporal API (目前 14-01-2023 还没有游览器支持)

6. 不同类型的排序

避开!!! 或者自己强转类型到一致. 不要出现任何 'a' > 123 这种鬼东西.

7. 字母, 数排序

字母中如果出现数字怎么排序呢?

const values = ['1', 'b', '11', '3', 'a', '2'];
values.sort((a,b) => a.localeCompare(b, 'en-US')); // ["1", "11", "2", "3", "a", "b"]
values.sort((a,b) => a.localeCompare(b, 'en-US', { numeric: true })); // ["1", "2", "3", "11", "a", "b"]

需要加入 numeric. 但我上面说过了, 不要 order 2 个不同类型. 你看 SQL, C# order by 的结果都不会考虑 numeric 的.

如果对 C# 怎么实现 numeric 感兴趣, 可以看这篇: Stack Overflow – How do I sort strings alphabetically while accounting for value when a string is numeric? 里面有许多 hacking way 非常聪明.

Intl.Collator vs localeCompare

参考: 张鑫旭 – JS Intl对象完整简介及在中文中的应用

Intl.Collator 据说是比 localeCompoare 更 modern 一点.

两个的接口都差不多.

const chineses = ['差', '阿', '八'];
chineses.sort(new Intl.Collator('zh-CN').compare); // ["阿", "八", "差"] 

逆序

顺序之后利用 Array.reverse 实现逆序是很不错的招数.

不然就在自定义的时候返回相反逻辑. 比如顺序返回 -1 negative 的话, 想逆序就返回 1 positive.

Multiple Order By

这个只会出现在 order by object 上. 它的做法就是当第一个 property value 相同时, 不要返回 0.

而是继续 compare 第二个 property value.

总结

JS 的 Array.sort 原生几乎是不可以使用的. 它的逻辑是先强转所以 value 去 string 然后依据 Unicode 排序.

几乎只有 a-z 可以符合这个做法. 连 number array 都 sort 不正确了. 更不用提 null, undefined 这些鬼.

自定义 sort 可以完成所有需求. 但一定要留意所有 value 的可能性. JS 在 compare value 是会有许多奇葩的自动转换规则.

我们要尽量避开让它自动转换, 自己强转并且明确表明哪一个值比较小或大. 这样排序结果才能正确.