5

根据MDN 规范，Javascript 的 sort() 函数是“不稳定的”（不维护相同元素的输入顺序）。

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

这给我留下了一个问题。我有一组元素要排序 - 一旦排序，我想将它们标记为“已排序”，以便后续的排序尝试不会浪费大量时间发现它们已经排序（如果有任何变化，我可以取消标记它们） .

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

这说明了问题（在这里小提琴）

<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的一种变体，它“只是为了它的地狱”交换数组中的元素

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

4

1 回答 1

5

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

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

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

额外参数作为属性添加，并且可以在将元素添加回容器以保持清洁时删除。

于 2013-09-03T02:41:51.130 回答