JS配列関数sort実現メカニズム

1931 ワード

V 8のソースコードを通じて、JS配列の順序付けに関する奇妙な問題を見てください.
js配列を並べ替えるのは常識的なコードです.しかし、ずっと疑問に思っていたのは、sort関数はどうして1つの減算結果を配列要素の順序を変えることができますか?
var arr = [1,3,12,3,5,89]
//    ,    
arr.sort( function(a, b){
  return a-b;
});
//[1, 3, 3, 5, 12, 89]
今日探してみましたが、最も根本的な原因はsort関数の内部実装メカニズムです.sort()方法は比較関数compre(a,b)を受け入れます.この関数は2つの値を比較して、この2つの値の相対的な順序を説明するための数字を返します.1または0以上の正数を返すと位置を交換します.
具体的な実現方法については、異なるエンジンによる実現が異なる.
V 8エンジンのソト関数は、InsertionSortとQuickSortの2つだけを与えています.数が10以下の配列はInsertionSortを使い、10の大きい配列よりQuickSortを使います.v 8-array.jsソース
Mozilla/Firefox:規格並べ替え(jsarray.cnソース)
Webkit:下の階の実現にC++ライブラリの中のqsort()の方法(JSArray.cppソース)を使いました.
参照リンク2:https://www.cnblogs.com/huoxiao/p/10239284.html
参照リンク1:https://segmentfault.com/q/1010000007133473?_ア=1247880