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 では発生しません (少なくとも、ここにあるバージョンでは発生しません)。
毎回頼らずにこれを回避する方法についてのアイデアはありますか?? 実際の並べ替えははるかに複雑で、何百もの要素をチェックする必要があるため、不必要に繰り返したくないほど多くの時間がかかりますか?
編集して追加:配列インデックスを使用して配列を強制的に並べ替えることも試みましたが、それでも Chrome では機能しません。Chromeは、配列内の要素を「ただの地獄のために」交換するクイックソートのバリアントを使用しているようです
毎回頼る、ソートを完全にスキップする、または独自のアルゴリズムを実装する以外に選択肢はないようです...