算法原理
设有一组关键字｛K1， K2，…， Kn｝；排序开始就认为 K1 是一个有序序列；让 K2 插入上述表长为 1 的有序序列，使之成为一个表长为 2 的有序序列；然后让 K3 插入上述表长为 2 的有序序列，使之成为一个表长为 3 的有序序列；依次类推，最后让 Kn 插入上述表长为 n-1 的有序序列，得一个表长为 n 的有序序列。
具体算法描述如下：
- 从第一个元素开始，该元素可以认为已经被排序
- 取出下一个元素，在已经排序的元素序列中从后向前扫描
- 如果该元素（已排序）大于新元素，将该元素移到下一位置
- 重复步骤 3，直到找到已排序的元素小于或者等于新元素的位置
- 将新元素插入到该位置后
- 重复步骤 2~5
JavaScript 实现代码：
function insertionSort(array) {
function swap(array, i, j) {
var temp = array[i];
array[i] = array[j];
array[j] = temp;
}
var length = array.length,
i,
j;
for (i = 1; i < length; i++) {
for (j = i; j > 0; j--) {
if (array[j - 1] > array[j]) {
swap(array, j - 1, j);
} else {
break;
}
}
}
return array;
}
--
