算法原理
設(shè)有一組關(guān)鍵字｛K1茅逮， K2巧涧，…薯蝎， Kn｝；排序開始就認(rèn)為 K1 是一個(gè)有序序列谤绳；讓 K2 插入上述表長為 1 的有序序列良风，使之成為一個(gè)表長為 2 的有序序列；然后讓 K3 插入上述表長為 2 的有序序列闷供，使之成為一個(gè)表長為 3 的有序序列烟央；依次類推，最后讓 Kn 插入上述表長為 n-1 的有序序列歪脏，得一個(gè)表長為 n 的有序序列疑俭。
具體算法描述如下：
- 從第一個(gè)元素開始，該元素可以認(rèn)為已經(jīng)被排序
- 取出下一個(gè)元素婿失，在已經(jīng)排序的元素序列中從后向前掃描
- 如果該元素（已排序）大于新元素钞艇，將該元素移到下一位置
- 重復(fù)步驟 3，直到找到已排序的元素小于或者等于新元素的位置
- 將新元素插入到該位置后
- 重復(fù)步驟 2~5
JavaScript 實(shí)現(xiàn)代碼：
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;
}
--
