β

Array.prototype.sort 在不同浏览器中的差异和解决办法

携程UED 100 阅读
转载需注明出处。
如有错误欢迎指正。

引子

有个需求需要前端对数据进行排序。
DEMO中只对第三列的数据进行排序。
类似下图:
Dom结构如下图
sort_dom
用[].sort()来call一下。
排序方法代码如下图(注意标红的地方,用的是Arr的sort方法):
sort_code
我们看下排序效果(chrome ff 撒发日 ie6-11都是这个效果)

但是

当参与排序的item数量超过10的时候,奇怪的地方出现了。
/**
* 当item数量超过10个的时候
* chrome 的排序不能说是排错了。因为我们是对分数进行排序,单看分数这一列完全没有错误。
* 但是如果我们对应着ID 一起看的话 发现chrome比较坑爹,
* 当分数相同的时候 chrome会对两个item乱排,而且似乎毫无规律。
*/
废话不说,看下图。
第一张图谷爹的chrome             第二张是FF和撒发日测的
sort2google sort2FF

问题排查

为什么chrome好像有些不正常呢?
其实问题是出在 v8 在对 Array.prototype.sort这个方法的实现上做了一些优化,
v8,Array.js
传送门 https://code.google.com/p/v8/source/browse/trunk/src/array.js (有兴趣的可以去看下,需要梯子)
代码中做过判断,数量小于或等于10的时候 走的是插入排序(InsertionSort);否则快速排序(QuickSort)
对排序算法如果有了解的应该知道 InsertionSort是稳定的排序算法,QuickSort则是不稳定的算法。
对于排序算法稳定性本文不做阐述,不了解的朋友可以自行搜索。
伸手党见下图:
sort_v8_code

解决问题

既然浏览器对Array.prototype.sort的实现不一样,解决这个问题只要自己写一个排序算法就行了,是要追求效率还是稳定性自己可以根据业务需求控制。
帖一个稳定排序算法-插入排序(insertSort)的代码。
这里是直接挂在 Array.prototype上面。
sort_insertsort
再来看下效果
sort2
END
作者:携程UED
携程旅行前端开发团队

发表评论