深色模式
插入排序
原理
插入排序，假设排序第 i 个数据， 数据内容记作 num ，则 i 之前的数据已经排好， i 之后的数据还没有处理，则将 第 i 条数据插入前 i-1 条数据之中。因此方案是，从 第 i-1 条开始比较，如果第 i-1 条数据 > num ， 则 num 所在最终位置一定在 i -1 之前的位置。将 第 i-1 条数据后移一位， 继续向前进入下次循环，知道找到核实位置。
插入排序：可以理解为打牌时排列纸牌顺序。
性质
稳定性
插入排序是一种稳定的排序算法。
时间复杂度
插入排序的最优时间复杂度为
插入排序的最坏时间复杂度和平均时间复杂度都为
伪代码实现
python
INPUT: An Array A consisting of n elements
OUTPUT: A will be sorted in nondecreasing order stably
Method:
# 从第二个数据开始
for i <- 2 to n
key <- A[i]
j <- i-1
while j > 0 and A[j] > key
A[j+1] = A[j]
j <- j-1
A[j+1] = keyJS 实现算法
js
Array.prototype.insertSort = function () {
let arr = this.slice(0);
for (var i = 1; i < arr.length; i++) {
var j = i - 1;
var num = arr[i];
while (j >= 0 && arr[j] > num) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = num;
}
return arr;
};
var a = [3, 5, 3, 0, 8, 6, 1, 5, 8, 6, 2, 4, 9, 4, 7, 0, 1, 8, 9, 7, 3, 1, 2, 5, 9, 7, 4, 0, 2, 6];
console.log(a.insertSort());