[演算法(Algorithm)] 插入排序法(Insertion Sort)

• 插入排序作法：
  • 將資料分成已排序、未排序兩部份
  • 依序由未排序中的第一筆(正處理的值)，插入到已排序中的適當位置
    • 插入時由右而左比較，直到遇到第一個比正處理的值小的值，再插入
    • 比較時，若遇到的值比正處理的值大或相等，則將值往右移
• 時間複雜度(Time Complexity)
  • Best Case：Ο(1)
    • 當資料的順序恰好為由小到大時，每回合只需比較1次
  • Worst Case：Ο(n²)
    • 當資料的順序恰好為由大到小時，第i回合需比i次
  • Average Case：Ο(n²)
    • 第n筆資料，平均比較n/2次
• 空間複雜度(Space Complexity)：θ(1)
• 穩定性(Stable/Unstable)：穩定(Stable)
• Demo:
• 演算法
  • JS1
  • JS2

  var insertionSort = function(data){
      var i, j, tmp;
      for(i = 1; i < data.length; i++){
          tmp = data[i];
          for( j=i; j > 0 && tmp < data[j-1]; j-- )
              data[j] = data[j-1];        
          data[j] = tmp;
      }
  };
  

  var insertionSort = function(data){
      for(var i = 1; i < data.length; i ++){
          var tmp = data[i];          // tmp = 正處理的值
          var j = i - 1;
          while( j > -1 && tmp < data[j]){
              data[j+1] = data[j];    // 向右移
              j--;
          }
          data[j+1] = tmp;            // 插入新值
      }   
  };