/ JavaScript  

意料之外的排序(Sort "Bug")

数字排序

先抛出一个你一定遇到过的问题

当我们对一个数组进行排序的时候,你会发现结果诶??再仔细一看,怎么像是感觉根据字符串排序了,我传入的明明是数字..


★ 所以第一个点,我们要记住compareFunction默认是会转换为字符串按照字符的 Unicode 位点进行排序的

1
arr.sort([compareFunction])

数字排序要这样写

1
2
3
4
5
6
7
arr.sort(function(a, b) {
return a - b
})

// or

arr.sort((a, b) => a - b)

中文排序

上面提到 compareFunction 默认是按照 Unicode 点位进行比较的,那么中文肯定是不能如图这样排序了

这时候,你需要一个转化为其他字符集来比较的方法 String.localeCompare

1
referenceStr.localeCompare(compareString[, locales[, options]])

实现 ↓

localeCompare 可以指定具体语言进行字符的比较,不过这个目前坑比较多 需要小心使用,比如

  • 兼容性上还比较新,需要注意 (IE11+、safari10+)

  • 比较结果的约定是正负数,不同浏览器下返回不一致,所以不要指定数值做结果判断

  • 大数据情况如何优化

  • locales 规范众多,不同浏览器不是都有对应实现,甚至实测不同浏览器同一 locals 下排序结果也有不同


So, 这么麻烦有没有其他方案呢?

你可以转成拼音再比较啊,虽然丢失了我们伟大的声调.. 出门右上方 Github ..

对象排序

我不知道你们有没有遇到过,理论上对象排序(根据对象某一个字段排序)按照如下方式是可行的,但是会出现错误

1
2
3
4
5
6
7
8
9
10
11
12
13
var items = [
{ name: 'Edward', value: 21 },
{ name: 'Sharpe', value: 37 },
{ name: 'And', value: 45 },
{ name: 'The', value: -12 },
{ name: 'Magnetic' },
{ name: 'Zeros', value: 37 }
];

// sort by value
items.sort(function (a, b) {
return (a.value - b.value)
});

我当时经历的实际现象是由于mqtt队列存储的时间不可靠,而且今日的数据是全量返回没有分页设计,这就需要前端对可能大量话数据进行排序,大概就是这样一个数据 [{…..,time: 1551455510878000},{…..,time: 1551455510878000},…]。出问题的用户当时的数据量是80+条

由于当时紧急处理也没把用户的数据存一份,我实际模拟的几次,包括把 time 抽成一维数组进行校验,还是按照数组对象形式,都没有在同样的环境里复现这个问题

(模拟一百条数据,最后一句检测有没有排序错误 ↓)

(模拟一百条数据,最后一句检测有没有排序错误 ↓)

(模拟一百条数据,加上洗牌算法,最后一句检测有没有排序错误 ↓)

解决方案是将 time 和 对应数据索引位 做了个映射关系 (map),,由于非理想情况下可能出现同一时间多条对话,实际是 time 对应多个索引位,顺序依赖数据源 (所以还是有风险,我这个项目的数据源并不靠谱)

参考如下吧

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

var data = [{time}, {time}, {time}, {time}, ...]
var output = []

var map = {}
var timeArr = []
for (var i in data) {
timeArr.push(data[i].time)
map[data[i].time] = map[data[i].time] || []
map[data[i].time].push(i)
}

timeArr.sort(function(a, b) {return a - b})
for (var i in timeArr) {
output.push( map[timeArr[i]].shift() )
}

稳定排序

有没有碰到过每次排序因为比较值的大小一样,然后每次排序一样的就忽前忽后、忽上忽下.. 比如表格,你点下排序、再重复多点几次看看,顺手还能反馈几个Bug

我想,你需要稳定排序

稳定排序:如果a原本在b前面,而a=b,排序之后a仍然在b的前面; 不稳定:如果a原本在b的前面,而a=b,排序之后a可能会出现在b的后面;

 

先上个找来的图 ↓

各个浏览器内核对排序算法的规划不太一样,没仔细查了,我们以 V8 来看

v8 在处理 sort 方法时,使用了插入排序和快排两种方案。当目标数组长度小于10时,使用插入排序;反之,使用快排

所以,原生 Sort 基本无法避免,更何况你需要兼顾各个内核,另外参考以下建议

  1. 放弃原生Sort, 另外实现表中稳定排序算法,开源库应该有很多
  2. 参考上面 对象排序 中的做索引位映射表也可以解决
  3. 让后端搞吧