よくある並べ替え方法(javascript)
2213 ワード
泡の並べ替え
重複した訪問は並べ替えられた数列で、一回に2つの要素を比較します.順序が間違ったら交換します.このアルゴリズムの名前の由来は、小さい元素ほど交換を通じて徐々に数列の先端に浮くからです.
並べ替えの挿入
整列されていないデータの場合は、順序付けされたシーケンスの後から前へスキャンし、該当する位置を見つけて挿入します.
クイックソート
一度の並べ替えで並べ替えたいデータを2つの部分に分割し、左の部分は右の部分より小さく、この方法で並べ替えを続けます.
(後で補充します.)ωカンヌ
重複した訪問は並べ替えられた数列で、一回に2つの要素を比較します.順序が間違ったら交換します.このアルゴリズムの名前の由来は、小さい元素ほど交換を通じて徐々に数列の先端に浮くからです.
let arr = [3,12,5,8,19,21,1,15];
for (let i = 0; i < arr.length - 1; i++) {
for (let j = 0; j arr[j+1]) {
let temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
ステップ:一番外側の層の循環回数と配列長は等しいです.最初の循環は、すべての項目の2つのコントラストで、行列の中で最大の数字が最後に配置されます.初めての比較結果:[3,12,5,8,19,1,15,21];
一番大きな数字が選ばれたので、最後の数字は比較に入らなくてもいいです.第二ラウンドは第一項から最後から第二項まで比較します.第二の比較結果:[3,12,5,8,1,15,19,21];
この類推をもって最後まで比較して結果を出す.比较するたびに最大を后ろに移すことができるので、内层のサイクルは毎回iを引いています.iは何回かの比较を行ったのです.並べ替えの挿入
整列されていないデータの場合は、順序付けされたシーケンスの後から前へスキャンし、該当する位置を見つけて挿入します.
let arr = [3,12,5,8,19,21,1,15];
for (let i = 1; i < arr.length; i++){
for (let j = 0; j < i; j++){
if(arr[j] > arr[i]){
arr.splice(j, 0, arr[i]);
arr.splice(i+1, 1);
}
}
}
ステップ:最外層の循環回数と配列長は同じです.i=1の場合、内層サイクルは1回、すなわちjは0、第一項と第二項の比較を行い、第一項が第二項より大きい場合、jの位置、すなわち第一項の位置にiの数字、すなわち第二項を挿入して、i位置自体の数字を削除する.i=2の場合、第一項、第二項は第三項と比較し、第三項より大きい場合は操作を行う.第二項は第三項より大きい.//
[3,5,12,5,8,19,21,1,15]
//
[3,5,12,8,19,21,1,15]
後はこれを類推して、それぞれの層は循環して、一番大きいのを後ろに変えます.これは後ろのデータを一つずつ前のどの位置に置くかを比較してから交換するということです.クイックソート
一度の並べ替えで並べ替えたいデータを2つの部分に分割し、左の部分は右の部分より小さく、この方法で並べ替えを続けます.
Array.prototype.quick_sort = function() {
var len = this.length;
if(len <= 1){
return this.slice(0);
}
var left = [];
var right = [];
var mid = [this[0]];
for (var i = 1; i < len; i++) {
if (this[i] < mid[0]){
left.push(this[i]);
}else{
right.push(this[i]);
}
}
return left.quick_sort().concat(mid.concat(right.quick_sort()));
}
let arr = [3,5,12,8,19,21,1,15];
arr = arr.quick_sort();
ステップ:配列の最初の項目を基準項目とし、すべての基準項目より小さいのは左で、基準項目より大きいのは右です.この時のleftは[1]、rightは[5,12,8,19,21,15]です.leftは長さが1なので、必ず最小となります.ここでleftは並べ替えを実行する必要がありません.ナイトの最初の項目は5で、残りは全部ナイト配列に並びます.この時rightは[12,8,19,21,15]です.これをもって類推する(後で補充します.)ωカンヌ