运用逆向思维:插入排序
一句话总结
插入排序是基于 选择排序 的一种优化,将 nums[sortedIndex]
插入到左侧的有序数组中。对于有序度较高的数组,插入排序的效率比较高。
前文 选择排序所面临的问题 中分析了选择排序遇到的几个问题,然后逐步优化写出了 冒泡排序,使得排序算法具有稳定性,且能够在输入数组的有序度较高时提前终止,提升效率。
回顾一下,冒泡排序的关键点在于对下面这段代码的优化:
// 对选择排序进行第一波优化,获得了稳定性
void sort(int[] nums) {
int n = nums.length;
int sortedIndex = 0;
while (sortedIndex < n) {
// 在未排序部分中找到最小值 nums[minIndex]
int minIndex = sortedIndex;
for (int i = sortedIndex + 1; i < n; i++) {
if (nums[i] < nums[minIndex]) {
minIndex = i;
}
}
// 将 nums[minIndex] 插入到 nums[sortedIndex] 的位置
// 将 nums[sortedIndex..minIndex] 的元素整体向后移动一位
int minVal = nums[minIndex];
// 数组搬移数据的操作
for (int i = minIndex; i > sortedIndex; i--) {
// swap(nums[i], nums[i - 1])
nums[i] = nums[i - 1];
}
nums[sortedIndex] = minVal;
sortedIndex++;
}
}
为了避免 while 内存在两个 for 循环,我们使用了一种类似冒泡的方式逐步交换 nums[sortedIndex..]
中的逆序对,将最小值换到 nums[sortedIndex]
的位置。
好的,先停在这一步,让我们忘记冒泡排序的优化方法,你来思考一下,是否还有其他方法能够优化上述代码,把 while 循环中的两个 for 循环优化成一个 for 循环?
反向思维
上面的算法思路是:在 nums[sortedIndex..]
中找到最小值,然后将其插入到 nums[sortedIndex]
的位置。
那么我们能不能反过来想,在 nums[0..sortedIndex-1]
这个部分有序的数组中,找到 nums[sortedIndex]
应该插入的位置,然后进行插入呢?
当年我思考如何对插入排序进行优化时,是想到过这个思路的,因为我想利用数组的有序性呀:既然 nums[0..sortedIndex-1]
这部分是已经排好序的,那么我就可以用二分搜索来寻找 nums[sortedIndex]
应该插入的位置。
这样一来,上述代码中的内层第一个 for 循环,我可以给他优化成对数级别的复杂度。
但是仔细想想,用二分搜索好像是多此一举的。因为就算我用二分搜索找到了 nums[sortedIndex]
应该插入的位置,我还是需要搬移元素进行插入,那还不如一边遍历一遍交换元素的方法简单高效呢:
// 对选择排序进一步优化,想左侧有序数组中插入元素
// 这个算法有另一个名字,叫做插入排序
void sort(int[] nums) {
int n = nums.length;
// 维护 [0, sortedIndex) 是有序数组
int sortedIndex = 0;
while (sortedIndex < n) {
// 将 nums[sortedIndex] 插入到有序数组 [0, sortedIndex) 中
for (int i = sortedIndex; i > 0; i--) {
if (nums[i] < nums[i - 1]) {
// swap(nums[i], nums[i - 1])
int tmp = nums[i];
nums[i] = nums[i - 1];
nums[i - 1] = tmp;
} else {
break;
}
}
sortedIndex++;
}
}
插入排序
这个算法的名字叫做插入排序,它的执行过程就像是打扑克牌时,将新抓到的牌插入到手中已经排好序的牌中。
插入排序的空间复杂度是 ,是原地排序算法。时间复杂度是 ,具体的操作次数和选择排序类似,是一个等差数列求和,大约是 次。
插入排序是一种稳定排序,因为只有在 nums[i] < nums[i - 1]
的情况下才会交换元素,所以相同元素的相对位置不会发生改变。
初始有序度越高,效率越高
显然,插入排序的效率和输入数组的有序度有很大关系,可以举极端例子来理解:
如果输入数组已经有序,或者仅有个别元素逆序,那么插入排序的内层 for 循环几乎不需要执行元素交换,所以时间复杂度接近 。
如果输入的数组是完全逆序的,那么插入排序的效率就会很低,内层 for 循环每次都要对 nums[0..sortedIndex-1]
的所有元素进行交换,算法的总时间复杂度就接近 。
如果对比插入排序和冒泡排序,插入排序的综合性能应该要高于冒泡排序。
直观地说,插入排序的内层 for 循环,只需要对 sortedIndex
左侧 nums[0..sortedIndex-1]
这部分有序数组进行遍历和元素交换,大部分非极端情况下,可能不需要遍历完 nums[0..sortedIndex-1]
的所有元素;而冒泡排序的内层 for 循环,每次都需要遍历sortedIndex
右侧 nums[sortedIndex..]
的所有元素。
所以冒泡排序的操作数大约是 ,而插入排序的操作数会小于 。
你可以把插入排序的代码拿去力扣第 912 题「排序数组」提交,它最终依然会超时,但可以说明算法代码的逻辑是正确的。之后的文章我们继续探讨如何对排序算法进行优化。