JavaScript的排序是“不稳定"的-我该如何解决? [英] Javascript's sort is 'unstable' - how do I get around this?
问题描述
根据 MDN规范，Javascript的sort()函数是不稳定"的(不为相同元素保持输入顺序).
According to the MDN spec, Javascript's sort() function is 'unstable' (does not maintain input order for identical elements).
具有讽刺意味的是，Firefox目前似乎尚未实现此功能-但Chrome似乎可以实现.
Ironically, it seems that Firefox currently doesn't implement this - but Chrome appears to.
这给我带来了一个问题.我有一组要排序的元素-排序后，我想将它们标记为已排序"，这样以后进行排序的尝试就不会浪费很多时间，因为它们已经被排序了(如果发生任何更改，我可以取消标记)
This leaves me with a bit of an issue. I have a set of elements to sort - once sorted I'd like to flag them as 'sorted' so that subsequent attempts to sort will not waste a lot of time discovering they're already sorted (I can unflag them if anything changes).
问题是，我的解决方案是在我的compare函数中返回"0"，但这意味着我只是对每个元素都返回等效性"，并且可以(并且将)对其进行洗牌.
Problem is, my solution for this is returning '0' in my compare function, but that means I'm simply returning 'equivalence' for every element and they can (and will) be shuffled.
这证明了问题所在(在这里拨弄)
<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中不会发生(至少不是我在这里看到的版本).
Run on Chrome you will see the middle element of the set move around on subsequent sorts - this doesn't happen on Mozilla (at least not the version I have here).
关于我如何解决此问题的任何想法，而不必每次都花时间??实际的排序要复杂得多，要检查100多个元素，所以要花很多时间，我不想不必要地重复?
Any ideas on how I can work around this without having to resort EVERY time?? The actual sort is much more complex and has 100s of elements to check so takes a LOT of time which I don't want to repeat unnecessarily?
编辑添加:我什至尝试使用数组索引来强制对数组进行排序，但是即使在Chrome上也不起作用. Chrome似乎使用了 Quicksort 的变体，该变体只是为了地狱"交换数组中的元素.它是
Editted to add: I even tried using the array index to force sorting the array in-order but even that doesn't work on Chrome. Chrome appears to use a variant of a Quicksort which swaps elements in the array 'just for the hell of it'
似乎我别无选择，只能每次都求助，完全跳过排序或实现我自己的算法...
Seems I've no option but to either resort every time, skip the sort entirely or implement my own algorithm...
推荐答案
下面是一个稳定的排序示例.它为原始项目索引添加了一个额外的参数，如果项目相等"，则使用该参数.该代码应可在任何使用的浏览器中使用.
Here is an example of a working stable sort. It adds an extra parameter for the original item index which is used if items are otherwise "equal". The code should work in any browser in use.
请注意，这只是一个示例，应进行修改以适合您的特定情况.
Note that it is an example only and should be modified to suit your particular circumstance.
<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>
额外的参数作为属性添加，当将元素重新添加到容器中以保持环境干净时，可以将其删除.
The extra parameter is added as an attribute and could be removed when elements are added back to the container to keep things clean.
这篇关于JavaScript的排序是“不稳定"的-我该如何解决?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
