javascript – 为什么在排序时重复元素出现在数组中？

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了javascript – 为什么在排序时重复元素出现在数组中？，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2044字，纯文字阅读大概需要3分钟。

内容图文

我知道如何使用Array.sort()在javascript中对数组进行排序,但我不知道在下面的代码中每次迭代时到底发生了什么.在某些点的代码中,一些重复的元素开始出现在数组中.我已经在很多网站上搜索了这个谜团的解释,但我不明白为什么会发生这种情况.在Chrome浏览器中运行此代码.我猜它是在浏览器的本机代码上运行的.但我想知道这背后的逻辑.

我知道排序是基于正负值和零值的返回,但为什么会出现重复元素？

var arr = [4, 3, 2, 1];
arr.sort(function(a, b) {
  document.getElementById("output").innerHTML += ("[" + arr + "] " + 'a = ' + a + ' b = ' + b + "<br>");
  return a - b;
});
document.getElementById("output").innerHTML += "[" + arr + "]";

<div id="output"></div>

解决方法:

简短的回答是这样的：

对于在阵列上运行的任何就地算法,不能保证阵列的中间值有效或完整. Chrome选择实现排序算法的方式有一些中间步骤,其中数组的值是重复的,并且不是原始数组的完整集合,但这是完全可以接受的,因为排序算法还没有完成.

TLDR版本：

如果你想知道这背后的确切逻辑,你可以查看Chrome在这里使用的V8 javascript引擎的源代码https://github.com/v8/v8/blob/master/src/js/array.js

特别是对于这种情况

For short (length <= 22) arrays, insertion sort is used for efficiency.

//This function was copied from the link above
function InsertionSort(a, from, to) {
  for (var i = from + 1; i < to; i++) {
    var element = a[i];
    for (var j = i - 1; j >= from; j--) {
      var tmp = a[j];
      var order = comparefn(tmp, element); //This is where your comparison function is called
      if (order > 0) {
        a[j + 1] = tmp;
      } else {
        break;
      }
    }
    a[j + 1] = element;
  }
};

逐步完成这个复制……

第一次比较：比较之前的数组[4,3,2,1]

i = 1,j = 0,tmp = a = 4,element = b = 3,order = 1,arr [1] = tmp = a = 4,arr [0] = element = b = 3

第二次比较：比较之前的数组[3,4,2,1]

i = 2,j = 1,tmp = a = 4,element = b = 2,order = 2,arr [2] = tmp = a = 4

第3次比较：比较之前的数组[3,4,4,1]

i = 2,j = 0,tmp = a = 3,element = b = 2(这仍然是外部for循环的内存),order = 1,arr [1] = tmp = a = 3,arr [0 ] =元素= b = 2

第4次比较：比较之前的数组[2,3,4,1] …

由此可以看出为什么值在数组中短暂重复,因为在插入排序中如何设置for循环.它被设置为以最少的次数写入数组,并且搜索值保存在内存中,因此数组的中间值不需要有效.

内容总结

以上是互联网集市为您收集整理的javascript – 为什么在排序时重复元素出现在数组中？全部内容，希望文章能够帮你解决javascript – 为什么在排序时重复元素出现在数组中？所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端