个人中心
gpt4 book ai didi

Javascript 排序是 'unstable' - 我该如何解决这个问题？

转载 作者：搜寻专家 更新时间：2023-11-01 04:09:37 25 4
gpt4 key购买 nike

根据MDN spec , Javascript 的 sort() 函数“不稳定”(不维护相同元素的输入顺序)。

具有讽刺意味的是，Firefox 目前似乎没有实现这一点——但 Chrome 似乎实现了。

这给我留下了一个小问题。我有一组元素要排序——排序后我想将它们标记为“已排序”，这样后续的排序尝试就不会浪费很多时间来发现它们已经排序(如果有任何变化我可以取消标记) .

问题是，我的解决方案是在我的比较函数中返回“0”，但这意味着我只是为每个元素返回“等价”，它们可以(并且将会)被打乱。

这证明了问题 ( fiddle here )

<head>
    <script>
        var firsttime=true;
        function test() {
            debugger;
            var elements = document.getElementById('test').children;
            var sortMe = [];
            for (var i=0; i<elements.length; i++)
                sortMe.push(elements[i]);
            sortMe.sort(function(a, b) {
                if (firsttime) {
                    if (a.innerText < b.innerText) return -1;
                    else if (a.innerText > b.innerText) return 1;
                    else return 0;
                } else {
                    return 0;
                }
            });
            var parent = document.getElementById('test');
            parent.innerHTML = "";
            for(var i = 0, l = sortMe.length; i < l; i++) {
                parent.appendChild(sortMe[i]);
            }
            firsttime=false;
        }
    </script>
</head>
<body>
<div id=test>
    <div>B</div>
    <div>D</div>
    <div>A</div>
    <div>C</div>
    <div>E</div>
    <div>B</div>
    <div>D</div>
    <div>A</div>
    <div>C</div>
    <div>E</div>
    <div>B</div>
    <div>D</div>
    <div>A</div>
    <div>C</div>
    <div>E</div>
</div>
<input type=button onclick=test()>
</body>

在 Chrome 上运行，您会看到集合的中间元素在随后的排序中四处移动——这在 Mozilla 上不会发生(至少我这里的版本不会)。

关于如何解决这个问题而不必每次都求助的任何想法？实际的排序要复杂得多，有 100 多个元素要检查，所以需要很多时间，我不想不必要地重复？

编辑添加:我什至尝试使用数组索引强制按顺序对数组进行排序，但即使这样在 Chrome 上也不起作用。 Chrome 似乎使用了 Quicksort 的变体它交换数组中的元素“只是为了它的 hell ”

似乎我别无选择，只能每次求助，完全跳过排序或实现我自己的算法...

最佳答案

这是一个工作稳定排序的例子。它为原始项目索引添加了一个额外参数，如果项目在其他方面“相等”则使用该参数。该代码应适用于任何正在使用的浏览器。

请注意，这只是一个示例，应根据您的具体情况进行修改。

<script type="text/javascript">

// Return the text content of an element depending on
// whether the textContent or innerText property is supported
function getText(el) {
  if (typeof el.textContent == 'string') {
    return el.textContent;
  } else if (typeof el.innerText == 'string') {
    return el.innerText;
  } else {
    // gather text nodes and concatenate values
    // trimmed as almost never used now
  }
}


function sortEm(){

  // Get the elements to sort
  var container = document.getElementById('container'); 
  var divs = container.getElementsByTagName('div');
  var els = [];

  // Convert collection to an array, add the current index for the element
  // as a data- property
  for (var i=0, iLen=divs.length; i<iLen; i++) {
    divs[i].setAttribute('data-sortIndex', i);
    els[i] = divs[i];
  }

  // Sort the array. If the textContent is equal, use
  // the original index
  els.sort(function(a, b) {
    var aText = getText(a);
    var bText = getText(b);

    if (aText < bText) return -1;
    if (aText > bText) return 1;
    return a.getAttribute('data-SortIndex') - b.getAttribute('data-sortIndex');
  })

  // Modify the content
  for (var j=0, jLen=els.length; j<jLen; j++) {
    container.appendChild(els[j]);
  }
}

</script>

<div id="container">
  <div style="background-color: red;">0</div>
  <div style="background-color: red;">2</div>
  <div style="background-color: blue;">0</div>
</div>
<button onclick="sortEm()">Sort divs</button>

额外的参数被添加为一个属性，当元素被添加回容器时可以被删除以保持干净。

关于Javascript 排序是 'unstable' - 我该如何解决这个问题？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/18564843/

25 4 0
文章推荐： ios - AFNetworking 3.x 多部分表单上传
文章推荐： ios - 如何从右到左关闭模态 ViewController？
文章推荐： ios - 使用类似于 SLComposeViewController 的 Swift 将 UIImage 发布到 Instagram
文章推荐： c# - 使用参数从 JavaScript 调用 C# 方法
搜寻专家
个人简介

我是一名优秀的程序员,十分优秀！

滴滴打车优惠券免费领取
滴滴打车优惠券
全站热门文章
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com