插入排序
原理解析
- 从第一个元素开始,该元素可以认为已经被排序
- 取出下一个元素,在已经排序的元素序列中从后向前扫描
- 把取出的元素放到已排序的元素中间的合适位置
- 重复步骤2~3
范例演示
以下表格里,红色表示选中的待排序的数字,蓝色表示最终排好的数字。
第一轮:
- 对于第一个元素(红色),变成已排序元素(蓝色)
第二轮:
- 对于第二个元素,和已排序元素(蓝色数字)比较,插入到已排序元素中合适的位置(8放到10前面,之后都变成已排序元素)
第三轮:
- 对于第三个元素,和已排序元素(蓝色数字)比较,插入到已排序元素中合适的位置(9放到8和10中间,之后变成已排序元素)
...
第一轮 | 10 | 8 | 9 | 47 | 3 |
10 | 8 | 9 | 47 | 3 | |
第二轮 | 10 | 8 | 9 | 47 | 3 |
8 | 10 | 9 | 47 | 3 | |
第三轮 | 8 | 10 | 9 | 47 | 3 |
8 | 9 | 10 | 47 | 3 | |
第四轮 | 8 | 9 | 10 | 47 | 3 |
8 | 9 | 10 | 47 | 3 | |
第五轮 | 8 | 9 | 10 | 47 | 3 |
3 | 8 | 9 | 10 | 47 |
实现方式
插入法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)
效率测试
下面我们测试排序性能
let arr = randomArr(10000, 100)
console.time('sectionSort')
insertionSort(arr)
console.timeEnd('sectionSort')
function randomArr( arrLen = 100, maxValue = 1000 ) {
let arr = []
for(let i = 0; i < arrLen; i++) {
arr[i] = Math.floor((maxValue+1)*Math.random())
}
return arr
}
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
}
}
}
}
经浏览器测试,对于长度为10000的数组,排序约需要76ms(一次样本), 对于长度为100000的数组,排序约需要 8314ms(一次样本)。可以看出,数组长度增加10倍,排序时间约增加100倍
复杂度分析
时间复杂度为 O(n^2) ,和上面的测试基本一致