並べ替えアルゴリズム--データ構造とアルゴリズムのjavascriptは第12章を説明します.

8480 ワード

JavaScript

並べ替えは、一般的な機能であり、データのセットを指定し、並べ替えを行います.
その前に、基本的な作業を準備したいです.自動的に配列を生成し、このグループのデータを任意の処理ができます.

/**
     *     ，  
     * @param numElements
     * @constructor
     */
    function CArray(numElements){
        var me = this;
        me.dataStore = [];
        me.pos = 0;
        me.numElements = numElements;
        me.insert = insert;
        me.toString = toString;
        me.clear = clear;
        me.setData = setData;
        me.swap = swap;
        me.bubbleSort = bubbleSort;
        me.selectionSort = selectionSort;
        me.insertionSort = insertionSort;
 
        for(var i=0;i<numElements;++i){
            me.dataStore[i] = i ;
        }
        function insert(element){
            me.dataStore[me.pos++] = element;
        }
        function toString(){
            var restr = "";
            for ( var i = 0; i < me.dataStore.length; ++i ) {
                restr += me.dataStore[i] + " ";
                if (i > 0 & i % 10 == 0) {
                    restr += "
";
                }
            }
            return restr;
        }
        function clear(){
            for(var i=0;i<me.dataStore.length;++i){
                me.dataStore[i]=0;
            }
        }
        function setData(){
            for ( var i = 0; i < me.numElements; ++i ) {
                me.dataStore[i] = Math.floor(Math.random() * (me.numElements + 1));
            }
        }     
}

用例:

var n= 10000;
var mynums = new CArray(n);
mynums.setData();

次は並べ替えアルゴリズムの実装です.
泡の並べ替え

//      
//                      。
function bubbleSort(){
    var elen = me.dataStore.length;
    var temp ;
    for(var outer = elen; outer>=2;--outer){
        for(var inner = 0;inner<=outer -1; ++inner){
            if(me.dataStore[inner]>me.dataStore[inner+1]){
                swap(me.dataStore,inner,inner+1)
            }
        }
        //console.log(me.toString()) //        。
    }
}

テスト:

var n= 10000;
console.time("bubble")
//    
var mynums = new CArray(n);
mynums.setData();
mynums.bubbleSort();
console.timeEnd("bubble")

並べ替えを選択
配列の先頭から並べ替えを選択し、最初の要素と他の要素を比較します.すべての要素をチェックした後、最小要素は配列の最初の位置に置かれます.そしてアルゴリズムは第二の位置から続けます.このプロセスは常に行われており、配列の最後から2番目の位置に行くと、すべてのデータがソートされます.

//    
//             ，                 
function selectionSort(){
    var min,temp ;
    for(var outer = 0;outer<=me.dataStore.length-2;++outer){
        min = outer;
        //              （         ，         ）
        for(var inner = outer+1;inner<=me.dataStore.length-1;++inner){
            if(me.dataStore[inner]<me.dataStore[min]){
                min = inner ;
            }
        }
        swap(me.dataStore,outer,min)
        //console.log(me.toString()) //        。
    }
}

テスト:

var n = 1000;
//    
var mynums = new CArray(n);
mynums.setData();
mynums.selectionSort();
 
console.timeEnd("select")

並べ替えの挿入:
並べ替えを挿入すると、2つのループがあります.外循環は配列要素を順番に移動させ、内側循環は対外循環で選択された要素とその後ろの要素を比較します.外側のループで選択した要素が内側のループで選択した要素より小さい場合、配列要素は右に移動し、内側のループのこの要素の位置を空けます.

//    
//         ，   ，    (                ，             ,         ）
function insertionSort(){
    var  temp,inner;
    for(var outer=1;outer<=me.dataStore.length-1;++outer){
        temp = me.dataStore[outer];
        inner = outer;
        while(inner>0&&(me.dataStore[inner-1]>=temp)){
            me.dataStore[inner]=me.dataStore[inner-1];
            --inner;
        }
        me.dataStore[inner]=temp;
       // console.log(me.toString()) //        。
    }
}

テスト:

//    
var mynums = new CArray(n);
mynums.setData();
mynums.insertionSort();
 
console.timeEnd("insert")

詳細な並べ替え
詳細なデータ並べ替えアルゴリズム.これらは、一般的に、大規模なデータセットを処理するための最も効率的なソートアルゴリズムと考えられており、それらが処理するデータセットは数百万個以上の要素に達することができ、数百個または数千個だけではない.
ヒルの並べ替え
ヒルの並べ替えの動作原理は、順序付けの過程で比較される要素間の距離がどれぐらいあるかを示す間隔のシーケンスを定義することによって、まず距離の遠い要素を比較します.このスキームを用いて,隣接元素を簡単に比較すると,正しい位置から遠い要素をより速く適切な位置に戻すことができる.
第一版:

//    
//                    ，          。                           。
//          ？                 Marcin Ciura 2001      701 301 132 57 23 10 4 1
function shellsort(){
    for (var g = 0; g < this.gaps.length; ++g) {
        for (var i = this.gaps[g]; i < this.dataStore.length; ++i) {
            var temp = this.dataStore[i];
            for (var j = i; j >= this.gaps[g] && this.dataStore[j-                                this.gaps[g]] > temp;
                 j -= this.gaps[g]) {
                this.dataStore[j] = this.dataStore[j - this.gaps[g]];
            }
            this.dataStore[j] = temp;
        }
    }
}
//      
function setGaps(arr){
    me.gaps = arr;
}

私たちは固定的な間隔のシーケンスに従う必要があります.数の違うデータがある場合は、固定間隔シーケンスは現在のプログラムに適用されませんので、動的に間隔を設定する必要があります.
第二版:

//    （         ）
function  shellsort1(){
    var N = this.dataStore.length;
    var h = 1;
    while (h < N/3) {
        h = 3 * h + 1;
    }
    while (h >= 1) {
        for (var i = h; i < N; i++) {
            for (var j = i; j >= h && this.dataStore[j] < this.dataStore[j-h];j -= h) {
                swap(this.dataStore, j, j-h);
            }
        }
        h = (h-1)/3;
    }
}

テスト:

console.time("shell")
//    
var mynums = new CArray(n);
mynums.setData();
mynums.shellsort();
 
console.timeEnd("shell")
console.time("shell1")
//    
var mynums = new CArray(n);
mynums.setData();
mynums.shellsort1();
 
console.timeEnd("shell1")

並べ替え
一連の順序を並べたサブシーケンスを一つの大きな完全な順序に統合する.私たちは2つの並べ替えのサブアレイが必要です.そして、データサイズを比較することによって、最初に最小のデータから挿入を開始し、最後に結合して第3の配列が得られます.一番下の規格と並べ替えは、再帰的(データが多いと再帰的に深すぎる)必要があるので、ボトムから上の規格を取って並べ替えます.このアルゴリズムは、最初にデータセットを一つの要素だけの配列に分解します.その後、左右のサブアレイのセットを作成することによって、それらを徐々に統合し、各連結ごとに、最後に残ったこの配列のすべてのデータが完全にソートされるまで、順序付けされたデータを一部保存します.
コード:

function mergeSort() {
    if (this.dataStore.length < 2) {
        return;
    }
    var step = 1;
    var left, right;
    while (step < this.dataStore.length) {
        left = 0;
        right = step;
        while (right + step <= this.dataStore.length) {
            mergeArrays(this.dataStore, left, left+step, right, right+step);
            left = right + step;
            right = left + step;
        }
        if (right < this.dataStore.length) {
            mergeArrays(this.dataStore, left, left+step, right, this.dataStore.length);
        }
        //   
        step *= 2;
    }
}
function mergeArrays(arr, startLeft, stopLeft, startRight, stopRight) {
    var rightArr = new Array(stopRight - startRight + 1);
    var leftArr = new Array(stopLeft - startLeft + 1);
    k = startRight;
    //      
    for (var i = 0; i < (rightArr.length-1); ++i) {
        rightArr[i] = arr[k];
        ++k;
    }
    //      
    k = startLeft;
    for (var i = 0; i < (leftArr.length-1); ++i) {
        leftArr[i] = arr[k];
        ++k;
    }
    rightArr[rightArr.length-1] = Infinity; //    
    leftArr[leftArr.length-1] = Infinity; //    
    //  
    var m = 0;
    var n = 0;
    for (var k = startLeft; k < stopRight; ++k) {
        if (leftArr[m] <= rightArr[n]) {
            arr[k] = leftArr[m];
            m++;
        } else {
            arr[k] = rightArr[n];
            n++;
        }
    }
    //console.log("left array - ", leftArr);
    //console.log("right array - ", rightArr);
}

テスト:

console.time("mergeSort")
//    
var mynums = new CArray(n);
mynums.setData();
mynums.mergeSort();
 
console.timeEnd("mergeSort")

テストによって、規格化と順序付けはヒルの並べ替え効率と同じぐらいであることが分かりました.(10000個のデータ)
早送り
簡単に言えば、データを「基準値」よりも大きいまたは小さい2つの部分に分解し、再帰的に完成するまでに.
コード

function qSort(arr) {        
    if (arr.length == 0) { 
        return [];        
    }
    var left = [];
    var right = [];
    var pivot = arr[0];
    for (var i = 1; i < arr.length; i++) {
 
        if (arr[i] < pivot) { 
            left.push(arr[i]);        
        } else { 
            right.push(arr[i]);
        } 
    }
    return qSort(left).concat(pivot, qSort(right)); 
}

テスト:

console.time("qSort")
//    
var mynums = new CArray(n);
mynums.setData();
var list = mynums.getData();
mynums.qSort(list);
 
console.timeEnd("qSort")

面白い一節です.