文章目录
插入排序
1 动画
2 思想
一般人打扑克牌，整理牌的时候，都是按牌的大小（从小到大或者从大到小）整理牌的，那每摸一张新牌，就扫描自己的牌，把新牌插入到相应的位置。
插入排序的工作原理：通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
3 解法
var insertionSort = function(array) {
var len = array.length;
if(len <= 1) return;
var preIndex, current;
for (var i = 1; i < len; i++) {
preIndex = i - 1; // 前一个元素的下标
current = array[i]; // 当前元素
while (preIndex >= 0 && current < array[preIndex]) {
array[preIndex+1] = array[preIndex]; // 将元素往后挪一位
preIndex--; // 下标前移
}
if (preIndex+1 != i) { // 如果相等，证明该数比已排序的序列都大，就不需要进行赋值操作了
array[preIndex+1] = current; // 将当前元素插入到已排序序列中
}
}
return array;
}
4 分析
时间复杂度
-
最佳情况：
O(n) -
最差情况：
O(n²) -
平均情况：
O(n²)
空间复杂度
O(1)
稳定性
稳定。