基本思想：把要排序的數(shù)組分成兩部分舅锄，第一部分為已經(jīng)排好序的蔚舀，另一部分為待排序部分附较。每次從待排序部分拿一個(gè)元素吃粒，和已排序部分元素依次進(jìn)行比較潦俺，并在適當(dāng)位置插入拒课。
// js實(shí)現(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]
