js実装ソートアルゴリズム(バブル、選択、挿入、二分挿入、高速、ヒル)

ソートの挿入

ソートを挿入する基本的な操作は、ソートされたソートテーブルにレコードを挿入することであり、レコード数が1増加した新しいソートテーブルのソートプロセスは、最初の要素からソートされたとみなすことができる.次の要素を取り出し、ソートされた要素シーケンスで後から前へスキャンします.エレメント(ソート済み)が新しいエレメントより大きい場合は、エレメントを次の位置に移動します.並べ替えられた要素が新しい要素より小さいか等しい場所が見つかるまで、手順3を繰り返します.新しい要素をその位置に挿入した後.手順2～5を繰り返します.

        /**
         *       
         * @param  {Array} arr        
         * @return {Array}               
         */
        function insertSort(arr){
            var len = arr.length;
             for (var i = 1; i < len; i++) {
              var key = arr[i];
             var j = i - 1;
              while (j >= 0 && arr[j] > key) {
                  arr[j + 1] = arr[j];
                  j--;
              }
             arr[j + 1] = key;
         }
        return arr;
        }

アルゴリズム解析
最適:入力配列を昇順に並べます.T(n)=O(n)最悪の場合:入力配列は降順に配列される.T(n)＝O(n 2)平均:T(n)＝O(n 2)

二分挿入ソート

最初の要素から、この要素はソートされていると考えられます.次の要素を取り出し、ソートされた要素シーケンスの2分の1がそれより大きい数の最初の位置を検索します.新しい要素をその位置に挿入した後.上記の2つのステップを繰り返します

        /**
         *        
         * @param  {array} arr        
         * @return {array}            
         */
        function binaryInsertSort(arr){
            for (var i = 1; i < arr.length; i++) {
        var key = arr[i], left = 0, right = i - 1;
        while (left <= right) {
          var middle = parseInt((left + right) / 2);
          if (key < arr[middle]) {
            right = middle - 1;
          } else {
            left = middle + 1;
          }
        }
        for (var j = i - 1; j >= left; j--) {
          arr[j + 1] = arr[j];
        }
        arr[left] = key;
      }
    return arr;
    }

アルゴリズム解析
最適:T(n)=O(nlogn)最悪:T(n)=O(n 2)平均:T(n)=O(n 2)

ソートの選択

選択ソートとは,n−i次キーワード間の比較により,n−i−1個のレコードの中からキーワードの最小のレコードを選択し,i個目のレコードと交換することである.選択ソート(Selection-sort)は単純で直感的なソートアルゴリズムである.その動作原理:まず、ソートされていないシーケンスで最小(大)要素を見つけ、ソートされたシーケンスの開始位置に保存し、残りのソートされていない要素から最小(大)要素を探し続け、ソートされたシーケンスの最後に配置します.すべての要素がソートされるまで、このようにします.

function selectSort(arr){
        for(var i = 0; i < arr.length - 1; i++){
            var min = arr[i];
            for(var j = i + 1; j < arr.length - 1; j++){
                if(min > arr[j]){
                    var temp = min;
                    min = arr[j];
                    arr[j] = temp;
                }
            }
            arr[i] = min;
        }
        return arr;
    }

アルゴリズム解析
最適:T(n)＝O(n 2)最悪:T(n)＝O(n 2)平均:T(n)＝O(n 2)平均

バブルソート

バブルソートは交換ソートであり、その基本思想は、隣接するレコードのキーワードを2つ比較し、逆シーケンスであれば逆シーケンスのレコードがないまで交換することである.ソートする数列を繰り返し訪問し、2つの要素を一度に比較し、順序が間違っている場合は交換します.数列を訪問する作業は、交換が必要になるまで繰り返し、すなわち、その数列がソートされるまで行われる.このアルゴリズムの名前の由来は,小さな要素ほど交換を介して徐々に数列の先端に「浮かぶ」からである.

function bubbleSort(arr) {
        var len = arr.length;

        for (var i = 0; i < len - 1; i++) {
            var n = 0;
            for (var j = 0; j < len - i ; j++) {

                if(arr[j] < arr[j-1]){
                    n++;
                    console.log(n);
                    var temp = arr[j];
                    arr[j] = arr[j-1];
                    arr[j-1] = temp;
                }

            }
            if( n < 1){

                break;
            }
        }
        return arr;
    }

最適:T(n)＝O(n)最悪:T(n)＝O(n 2)平均:T(n)＝O(n 2)

クイックソート

(1)データセットで「基準」(pivot)として要素を選択する.(2)「データム」より小さいすべての要素は、「データム」の左側に移動します.「データム」より大きいすべての要素は、「データム」の右側に移動します.(3)「データム」の左と右の2つのサブセットに対して、すべてのサブセットが1つの要素しか残っていないまで、最初のステップと2番目のステップを繰り返します.

function quickSort(arr){
        if (arr.length <= 1){return arr};
        var pivotIndex = Math.floor(arr.length / 2);
        var pivot = arr.splice(pivotIndex,1)[0];
        var left = [];
        var right = [];
        for (var i = 0; i < arr.length; i++){
            if(arr[i] < pivot) {
                left.push(arr[i]);
            }else{
                right.push(arr[i]);
            }
        }
        return quickSort(left).concat([pivot],quickSort(right));
    }

アルゴリズム解析
最適:T(n)=O(nlogn)最悪:T(n)=O(n 2)平均:T(n)=O(nlogn)

ヒルソート

ヒルソートの本質は、パケット挿入ソートであり、この方法はインクリメンタルソートの縮小とも呼ばれる.この方法の基本思想は、まず、整列する要素のシーケンス全体をいくつかのサブシーケンス(ある「増分」を隔てた要素からなる)に分割してそれぞれ直接挿入ソートを行い、その後、順次増分を縮小してソートを行い、このシーケンスの要素が基本的に秩序化されている(増分が十分小さい)場合、全体の要素を一度直接挿入ソートすることである.直接挿入ソートは,要素が基本的に秩序化されている場合(最良に近い場合)に効率が高いため,ヒルソートは時間効率的に大きく向上した.ヒルソートアルゴリズム実装

function shallSort(array) {
 var increment = array.length;
 var i
 var temp; //  
 var count = 0;
 do {
    //    
   increment = Math.floor(increment / 3) + 1;
   for (i = increment ; i < array.length; i++) {
    console.log(increment);
     if (array[i] < array[i - increment]) {
       temp = array[i];
       for (var j = i - increment; j >= 0 && temp < array[j]; j -= increment) {
           array[j + increment] = array[j];
       }
       array[j + increment] = temp;
     }
   }
 }
 while (increment > 1)
 return array;
}