一思喊、原理解析
- 從第一個元素開始牙言，該元素可以認為已經(jīng)被排序
- 取出下一個元素鸭栖，在已經(jīng)排序的元素序列中從后向前掃描
- 把取出的元素放到已排序的元素中間的合適位置
- 重復步驟2~3
就像排隊一樣，依次每次挑一個同學肢簿，把該同學“插入”到已經(jīng)排好的部分隊伍里报慕。
二深浮、范例演示
以下表格里，紅色表示選中的待排序的數(shù)字眠冈，藍色表示最終排好的數(shù)字飞苇。
第一輪：對于第一個元素(紅色)，變成已排序元素(藍色)
第二輪：對于第二個元素蜗顽，和已排序元素(藍色數(shù)字)比較布卡，插入到已排序元素中合適的位置（8放到10前面，之后都變成已排序元素）
第三輪：對于第三個元素雇盖，和已排序元素(藍色數(shù)字)比較羽利，插入到已排序元素中合適的位置（9放到8和10中間，之后變成已排序元素）
...
三刊懈、實現(xiàn)方式
插入法JS 版
function insertionSort(arr) {
for(let i = 1; i < arr.length; i++) {
for(let j = 0; j < i; j++) {
if(arr[i] < arr[j]) {
arr.splice(j, 0, arr[i])
arr.splice(i+1, 1)
break
}
console.log(arr)
}
}
}
var arr = [10, 34, 21, 47, 3, 28]
insertionSort(arr)
console.log(arr)
插入法普通版
function insertionSort(arr) {
for(var i = 1; i < arr.length; i++) {
var temp = arr[i]
for(var j = i; j > 0 && arr[j-1] > temp; j--) {
arr[j] = arr[j-1]
}
arr[j] = temp
}
}
var arr = [10, 34, 21, 47, 3, 28]
insertionSort(arr)
console.log(arr)
復雜度分析
時間復雜度為 O(n^2)。
