基本思想：把要排序的數(shù)組分成兩部分，第一部分為已經(jīng)排好序的，另一部分為待排序部分。每次從待排序部分拿一個元素，和已排序部分元素依次進(jìn)行比較，并在適當(dāng)位置插入。

// js實現(xiàn)
function insertSort(arr){
  var x;
  for(var i = 1; i < arr.length; i ++){    // 外層循環(huán)進(jìn)行待排序部分的維護(hù)
    x = arr[i];        // 把要進(jìn)行排序的值緩存起來，避免覆蓋后丟失
    for(var j = i - 1; arr[j] > x; j --){    // 內(nèi)層循環(huán)進(jìn)行已排序部分的維護(hù)
      arr[j + 1] = arr[j];    // 將元素依次向后挪
    }
    if(arr[j + 1] != x ){
      arr[j + 1] = x;  // 在適當(dāng)位置插入
    }
  }
  return arr;
}


var arr = [3,1,2,5,8,4,7,2,9];
var result = insertSort(arr);
console.log(arr);    // [1, 2, 2, 3, 4, 5, 7, 8, 9]