JavaScript中的sort方法是'不稳定'的 - 我该如何避免这种情况？

Question

JavaScript中的sort方法是'不稳定'的 - 我该如何避免这种情况？

javascriptsorting

5

根据MDN规范，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上不会发生这种情况（至少我这里的版本不会）。

有什么办法可以避免每次都要重新排序吗？实际排序更加复杂，并且需要检查数百个元素，所以需要很长时间，我不想重复不必要的工作。

编辑后添加：我甚至尝试使用数组索引来强制按顺序对数组进行排序，但即使在Chrome上也不起作用。Chrome似乎使用了Quicksort的变体，'just for the hell of it'交换数组中的元素。

看来我只能每次重新排序，跳过排序或者实现自己的算法...

- user834595

你是否有可用的次要排序键，可以给你一个唯一的排序顺序？ - mu is too short

在实际应用中，排序是一个复杂的算法，它查看DIV内容，因此寻找二级排序同样会很慢。我开始觉得我应该将整个东西标记为“干净”或“脏”，并且除非它被标记为“脏”，否则不尝试进行任何排序- 我只是想这样做可以仅对已更改的位进行排序... - user834595

除非我为元素添加一个排序位置并使用它，否则可能会起作用，但仍然需要“一些工作”，而不是“没有工作”。不稳定的事情意味着你必须做“一些工作”，不过我猜是这样吧？ - user834595

1

没有必要一定使用Javascript的sort函数（当不适合使用不稳定排序时）。你可以使用自己的稳定排序算法（实现广泛可用）。 - Greg Hewgill

1

@JohnPeat：你可以尝试这个问题的答案：在JavaScript中实现快速稳定排序算法。 - Greg Hewgill

显示剩余2条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- RobG · Accepted Answer

这是一个稳定排序的工作示例。它添加了一个额外的参数来表示原始项目索引，如果项目“相等”，则使用该参数。该代码应在任何正在使用的浏览器中运行。

请注意，这仅是一个示例，应根据您特定的情况进行修改。

<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>

额外的参数会被添加为属性，并且当元素被添加回容器中时可以删除，以保持整洁。