JS順序付けアルゴリズム:発泡法、快速順序付け法、選択順序付け法、挿入順序付け法、ハッシュ順序付け
7066 ワード
JS順序付けアルゴリズム:発泡法、快速順序付け法、選択順序付け法、挿入順序付け法、ハッシュ順序付け
//
var arr = new Array(1000);
for (var i = 0; i < 1000; i++) {
arr[i] = (Math.round(Math.random() * 1000));
}
1.発泡法の並べ替え思想:配列の隣の二つの項目を比較し、前の項目が後の項目より大きい場合、交換位置を比較し、arr.length-1ラウンドを比較し、各ラウンドに最大の一桁を最後に置く.//
function sortArr(arr) {
for (var i = 0; i < arr.length - 1; i++) {// arr.length-1
for (var j = i + 1; j < arr.length; j++) {
if (arr[i] > arr[j]) {//
var temp = arr[i];//
arr[i] = arr[j];
arr[j] = temp;
}
}
}
return arr;
}
2.快速並べ替えの原理:並べ替えによって並べ替えられたデータを独立した二つの部分に分割し、その中の一部のすべてのデータは他の部分のすべてのデータよりも小さいです.そしてこの方法によって、この2つの部分のデータをそれぞれ迅速に並べ替えて、並べ替えのプロセスは(1)データセットの中で、1つの要素を「基準」として選択することができます.(pivot).(2)すべてが「基準」より小さい要素は、「基準」の左側に移動します.「基準」より大きい要素は、「基準」の右側に移動します.(3)ペアの「基準」の左と右の二つのサブセットは、第一歩と第二歩を繰り返して、すべてのサブセットが一つしか残っていないまで続けます.クイックソートの最悪の場合は、O(n)です.²),例えば、順番数列の早い列です.しかし、その屋台の希望時間はO(n logn)であり、O(n logn)記号に含まれる定数因子は小さく、複雑度より安定しています.O(n logn)の正規化順序よりも小さいです.したがって、ほとんどの順序が弱い乱数列に対しては、高速なソートは常に正規化と並べ替えより優れています.//
function sortQuick(arr) {
if (arr.length <= 1) {//
return arr;
} else {
var index = Math.floor(arr.length / 2);//
var len = arr.splice(index, 1);
var left = [];
var right = [];
for (var i = 0; i < arr.length; i++) {
if (arr[i] < len) {
left.push(arr[i]);
} else {
right.push(arr[i]);
}
}
return sortQuick(left).concat(len, sortQuick(right));
}
}
3.並べ替えの原理を選択します.並べ替えられるデータ要素の中から最小(または最大)を選択します.配列が比較範囲内の最初の要素の最小minと残りの比較を仮定して、仮定のこの元素より小さい場合はminをこの元素として、最小の位置を見つけてから、交換位置を比較すると、minをこの元素とする.一番小さい桁数を探して配列の一番前に置いてください.//
function sortSelect(arr) {
for (var i = 0; i < arr.length; i++) {
var min = arr[i];
var index = i;
for (var j = i + 1; j < arr.length; j++) {
if (arr[j] < min) {
min = arr[j];
index = j;
}
}
if (index != i) {
var temp = arr[i];
arr[i] = arr[index];
arr[index] = temp;
}
}
}
4.並べ替え法の挿入アルゴリズムは、並べ替えられる配列を2つの部分に分けます.第1の部分はこの配列のすべての要素を含んでいますが、最後の要素は除外されます.を選択します.最初の部分の並べ替えが完了したら、この最後の要素を並べられた最初の部分に挿入します.//
function sortInsert(arr) {
for (var i = 0; i < arr.length - 1; i++) {
var insert = arr[i + 1];
var index = i+1;
for(var j=i;j>=0;j--){
if(insert > arr[j]){
arr[j+1] = arr[j];
index = j;
}
}
arr[index] = insert;
}
}
5.ハッシュ並べ替えの原理:まず、列の要素のシーケンス全体をいくつかのサブシーケンスに分割し(ある「増分」からなる要素によって構成される)、それぞれ直接挿入順序付けを行い、その後、順次、増分を縮小して順序付けを行い、シーケンス全体の要素の基本的な順序(増分が十分小さい)になったら、全体の要素を直接挿入して並べ替えを行う.//
function sortShell(arr){
var len = arr.length,
temp,
gap = 1;
while(gap < len/3){
gap = gap*3+1;
}
for(gap;gap>0;gap = Math.floor(gap/3)){
for(var i=gap;ifor(var j=i-gap;j>0&&arr[j]>temp;j-=gap){
arr[j+gap] = arr[j];
}
arr[j+gap] = temp;
}
}
return arr;
}