基本思想：把要排序的数组分成两部分，第一部分为已经排好序的，另一部分为待排序部分。每次从待排序部分拿一个元素，和已排序部分元素依次进行比较，并在适当位置插入。
// js实现
function insertSort(arr){
var x;
for(var i = 1; i < arr.length; i ++){ // 外层循环进行待排序部分的维护
x = arr[i]; // 把要进行排序的值缓存起来，避免覆盖后丢失
for(var j = i - 1; arr[j] > x; j --){ // 内层循环进行已排序部分的维护
arr[j + 1] = arr[j]; // 将元素依次向后挪
}
if(arr[j + 1] != x ){
arr[j + 1] = x; // 在适当位置插入
}
}
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]
