順序付けアルゴリズム——javascriptアルゴリズムの実現

並べ替えSorting
並べ替えの基本概念
順序付けはコンピュータプログラムの設計において重要な動作であり、彼の機能はデータ要素(または記録)の任意の配列をキーワードに順序付けられたシーケンスに並べ替えることである.順序付けされた記録シーケンスには、2つ以上のキーワードが等しい記録が存在してもよく、順序付け前のRiはRjの前にある(すなわちi).
並べ替えの挿入
並べ替えO(n 2)を直接挿入します.
最も簡単な順序付けであり、基本的な操作は、順序付けされた順序表に記録を挿入することで、新たな順序表を作成し、1つ増分された順序表を記録する.

//      ，              ¬≥
function insertSort (Arr) {
     
  if (Arr.length <= 1) {
    return Arr;
  }
  var temp;

  for (var i = 1; i < Arr.length; i++) { // 1  ，       
    temp = Arr[i]; // temp        
    for (var j = i; j >= 0; j--) {
      if (temp < Arr[j]) {
        Arr[j + 1] = Arr[j]; // Arr[i]
      } else if (temp > Arr[j]) {
        break; //   ：        Arr[i]  Arr[j],     ，  
      }
      //   ， j  ，  
    }
    //  j  ， temp           
    Arr[j + 1] = temp;
  }

}; //insert  

その他の挿入順序

、並べ替えO(n 2)を半分割して挿入する.比較キーワードのサイズ数を減らすことにより、並べ替えアルゴリズムを最適化する.

番の挿入順序

テーブル挿入順序

ヒルソートO(n 3/2)
また、「縮小増分順序」とも呼ばれます.基本的な考えは、まず全列の記録シーケンスをいくつかのサブシーケンスに分割して、それぞれ直接挿入順序付けを行い、シーケンス全体における記録「基本的順序」を待ちながら、全体の記録を直接挿入順序付けを行います.

function shellSort(Arr) {
     
  var gap = Math.floor(Arr.length / 2);
  while (gap > 0) {
    for (var i = 0; i < Arr.length; i++) {
      var temp = Arr[i];
      for (var j = i; j >= gap && Arr[j - gap] > temp; j -= gap) {
        Arr[j] = Arr[j - gap];
      }
      Arr[j] = temp;
    }
    gap = Math.floor(gap / 2);
  }
  return Arr;
}; //shell  

クイックソート
泡立ちランキングbbble sort

//     ,
function bibbleSort(Arr) {
     
  for (var i = Arr.length - 1; i >= 0; i--) {
    for (var j = 0; j < i; j++) {
      if (Arr[j] > Arr[j + 1]) {
        swap(j, j + 1, Arr);
      }
    }
  }
  return Arr;
};

クイックソート

//           
// 1.     x=0,y=n-1, keyValuey=Arr[0],2. Arr[y]      ，  keyValue>Arr[y],  Arr[i] Arr[y]  ，3. Arr[x]    ， keyValue

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

並べ替えを選択
単純な選択順序

//                       
function selectSort(Arr) {
     
  for (var i = 0; i < Arr.length; i++) {
    for (var j = i; j < Arr.length; j++) {
      if (Arr[i] > Arr[j]) {
        swap(Arr, i, j);
      }
    }
  }
  return Arr;
}; //select  

ツリーの選択順序
留学する
ヒープソートheap sort
留
まとめてmerging sort O(m+n)を並べ替える.
最初のシーケンスはn個の記録を意味すると仮定すると、n個の秩序化されたサブシーケンスと見なされ、各サブシーケンスの長さは1であり、その後、両方がまとめられて、Math.flor(n/2)個の長さが2または1の秩序化されたサブシーケンスが得られるまで、もう2つがまとめられて、このように反復される.

function mergeSort (){
     
    var merge=function(left,right){
     
        var final=[];
        while(left.length&&right.length){
            final.push(left[0]<=right[0]?left.shift():right.shift());
        }
        return final.concat(left.concat(right));
    };

    var len=this.length;
    if(len<2){
        return this;
    }

    var mid=parseInt(len/2),
        _left=this.slice(0,mid),
        _right=this.slice(mid);
    return merge(_left.mergeSort(),_right.mergeSort());
};

基数並べ替えradix Sorting
留学する
各種並べ替えアルゴリズムの比較
以上使用したswap関数

//swap  
function swap(Arr, firPos, secPos) {
     
  var temp = Arr[firPos];
  Arr[firPos] = Arr[secPos];
  Arr[secPos] = temp;
  return Arr; //       
} //swap