JavaScriptを使って十大経典の並べ替えアルゴリズムを実現します.並べ替えを挿入します.

並べ替えコードを挿入して実現します.泡立て並べ替えや選び方はそんなに簡単ではありませんが、トランプをした人は秒で分かるはずです.手を並べたトランプのように、最初は左手が空いていて、テーブルの上の札が下にあります.それから、私たちは毎回テーブルからカードを持って行って、左手の中の正しい位置に挿入します.正しい位置を見つけるために、私たちは右から左までそれを手にした各カードと比較して、左手に持っている札はいつも並べ替えられています.これらの札はテーブルの上のプレートの中で一番上のプレートです.
1)アルゴリズムの原理
      並べ替え(Insertion-Sort)を挿入するアルゴリズム記述は簡単で直感的な並べ替えアルゴリズムである.その動作原理は、順序付けされたシーケンスを構築することによって、順序付けされていないデータに対して、順序付けされたシーケンスの中で後方から前へスキャンし、対応する位置を見つけて挿入することである.挿入順序付けは、実装では、一般的に、in-place順序付け(すなわち、O(1)までの追加の空間の順序付けのみを使用することができる)を使用しているので、後から前へスキャンする過程で、順序付けされた要素を逐次後方へ移動させ、最新の要素に挿入空間を提供する必要がある.
2)アルゴリズムの説明と実装
     一般的に、挿入順序は、配列上でin-placeを用いて実現される.具体的なアルゴリズムの説明は以下の通りである.
    <1>最初の要素から、この要素は並べ替えられたと考えられます.
    <2>次の要素を取り出して、順序付けされた要素系列の中で後から前へスキャンします.
    <3>要素が新しい要素より大きい場合は、要素を次の位置に移動します.
    <4>順序付けされた要素が新しい要素より小さいかまたは等しい位置を見つけるまで、ステップ3を繰り返します.
    <5>新しい要素をその位置に挿入した後、
    <6>手順2~5を繰り返します.
3)JavaScriptコードの実現

function insertSort(arr) {
       for (var i = 1; i < arr.length; i++) {
            var temp = arr[i];
            var j = i - 1;
            while (j >= 0 && arr[j] > temp) {
                arr[j + 1] = arr[j];
                 j--;
            }
            arr[j + 1] = temp;
        }
        return arr;
 }
var arr = [1, 45, 37, 5, 48, 15, 37, 26, 29, 2, 46, 4, 17, 50, 52];
console.log(insertSort(arr));

        挿入順序を変更: 挿入位置を検索する場合は、二分割検索を使用します.
ステップ:
        <1>最初の要素から、この要素は並べ替えられたと考えられます.          <2>次の要素を取り出し、並べ替えられた要素のシーケンスの中で、最初の大きさよりも大きな数の位置を二分的に検索します.          <3>新しい要素をその位置に挿入します. 

function binaryInsertionSort(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;
}
var arr = [1, 45, 37, 5, 48, 15, 37, 26, 29, 2, 46, 4, 17, 50, 52];
console.log(binaryInsertionSort(arr));

4)アルゴリズム分析
      最適な場合:入力配列は昇順に並べられます.T(n)=O(n)
      最悪の場合:入力配列は降順に配列されます.T(n)=O(n 2)
      平均状況:T(n)=O(n 2)