Web 技术研究所

我一直坚信着,Web 将会成为未来应用程序的主流

排序的坑

  很多编程语言都内置了排序功能,可是通常排序算法是规范不给定的。比如 ES5 对 JavaScript 的 sort 方法只要求其结果正确,并未提及具体应该使用何种排序算法。而且像 v8 这样的东西 sort 方法的实现更是用了混合排序,所以有时候排序结果是很难确定的。
  比如下面这个例子,如果没有加入索引作为子排序就会让排序键在相等时变得很不稳定。 <script>
var arr = [
  { 'v': 2, 'n': '2.0' },
  { 'v': 1, 'n': '1.0' },
  { 'v': 1, 'n': '1.1' },
  { 'v': 1, 'n': '1.2' }
];
// 如果把这个 6 改成 7 的话,在 Chrome 和 Firefox 会得到不同的结果
for(var i = 0; i < 6; i++) arr.push({ v: 0 });
arr.sort(function(left, right) {
  return right.v - left.v;
});
console.table(arr);
</script>
  上面这个不稳定就是因为 Chrome(42) 和 Firefx(37) 的排序算法不同造成的。在 v8 中如果元素未满 10 个会使用不同的排序算法。
  其实这点小差异对程序逻辑而言并没什么影响,但如果把这样奇怪的排序结果用于 MV* 的数据排序,结果也会造成造成大量不必要的 DOM 移动,影响到性能。又或者如果业务上牵涉到竞价排名之类的东西,造成的影响就很大了。
  我建议总是使用原数组索引作为最终子排序。或者说,刚拿到数据时就给所有数据加一个 index 属性来存储它们的默认位置,排序时用上确保一致性。
网名:
54.144.24.*
电子邮箱:
仅用于接收通知
提交 悄悄的告诉你,Ctrl+Enter 可以提交哦
神奇海螺
[查看全部主题]
各类Web技术问题讨论区
发起新主题
本模块采用即时聊天邮件通知的模式
让钛合金F5成为历史吧!
次碳酸钴的技术博客,文章原创,转载请保留原文链接 ^_^