基本思想
- 将一个元素插入一个有序数组中，使之成为更长的有序数组；
- 具体说来，需要从第 2 个数开始，依次把这个数插入到它之前 已经排好序 的部分，这样每一次都能得到比上一次更长的有序数组，直到数组整体有序；
- 循环不变的性质（循环不变量）：区间
nums[0, i)里保存了输入数组里的前 i 个元素，并且按照升序排序；
图解
插入方式一
逐个交换到前面合适的位置；
由于每一次数组里不同元素的交换，需要进行 多次 赋值操作，事实上可以减少赋值操作的次数，可以看方式二；
复杂度
-
时间复杂度：
- 最坏时间复杂度
O(N^2)，这里外层循环的变量 i 是与数组的长度 N 相关的，内层循环的变量 j 是与 i 相关的，间接与 N 相关，因此插入排序的时间复杂度是O(N^2) - 最好时间复杂度
O(N)，对一个已经有序的数组，使用插入排序，每一轮插入排序就只要看一下前面的那个元素，发现不能再往前面移动了，马上进入下一层循环；
- 最坏时间复杂度
-
空间复杂度：
O(1)
代码实现
let insertionSort = function (nums) {
let len = nums.length;
// 1. 将 nums[i] 插入到区间 [0, i) 使之成为有序数组
for (let i = 1; i < len; i++) {
// 2. 从后向前逐个交换，直到前面的那个元素小于或者等于当前要插入的这个元素
for (let j = i; j > 0; j--) {
if (nums[j - 1] > nums[j]) {
[nums[j - 1], nums[j]] = [nums[j], nums[j - 1]]; // 交换位置
} else {
break; // 插入后无需再比较，跳出循环
}
}
}
return nums;
}
插入方式二
先暂存当前变量，然后将前面的若干个元素逐个向后赋值；
相比第一种方式，只有一次赋值操作；
复杂度
-
时间复杂度：
- 最坏时间复杂度
O(N^2)，这里外层循环的变量 i 是与数组的长度 N 相关的，内层循环的变量 j 是与 i 相关的，间接与 N 相关，因此插入排序的时间复杂度是O(N^2) - 最好时间复杂度
O(N)，对一个已经有序的数组，使用插入排序，每一轮插入排序就只要看一下前面的那个元素，发现不能再往前面移动了，马上进入下一层循环；
- 最坏时间复杂度
-
空间复杂度：
O(1)
代码实现
let insertionSort = function (nums) {
let preIndex, temp;
// 1.外层循环对除了第一个元素之外的所有元素进行遍历
for (let i = 1; i < nums.length; i++) {
preIndex = i - 1;
temp = nums[i]; // 暂存这个元素
// 2. 大于 temp 的所有元素逐个后移
while (preIndex >= 0 && nums[preIndex] > temp) {
arr[preIndex + 1] = nums[preIndex];
preIndex--;
}
// 3.将 temp 处的值插入到合适的位置处
nums[preIndex + 1] = temp;
}
}
插入排序 VS 选择排序
「插入排序」和「选择排序」一样，也是应用了「减而治之」的思想，每一次插入的操作让 「未排定的部分」 减少 1 个元素，让 「已经排序的部分」 增加 1 个元素；
与「选择排序」不同的是，插入排序比较的方式是从后向前将依次看到的元素与待插入的元素进行比较，这一步操作不用比较完它前面所有的元素，即：插入排序内层循环可以提前终止，这一点是插入排序非常重要的性质；
插入排序」最好的时间复杂度为
O(N)；
打赏作者
您的打赏是我前进的动力
微信
支付宝
比较排序🔮 选择排序
上一篇
评论
