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;
}