根据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的变体,它可以交换数组中的元素"只是为了它的地狱"
似乎我没有选择,但每次都要求助,完全跳过排序或实现我自己的算法......
以下是工作稳定排序的示例.它为原始项目索引添加了一个额外参数,如果项目"等于",则使用该参数.代码应该在任何使用的浏览器中工作.
请注意,它仅是一个示例,应根据您的具体情况进行修改.
<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>
额外参数作为属性添加,并且可以在将元素添加回容器时将其删除以保持清洁.