插入排序

插入排序是基于选择排序的一种优化，将 nums[sortedIndex] 插入到左侧的有序数组中。对于有序度较高的数组，插入排序的效率比较高。

• 练习题目: 力扣第 912 题 数组排序，先不纠结时间复杂度。

想法

选择排序的思路是：在 nums[sortedIndex..] 中找到最小值，然后将其插入到 nums[sortedIndex] 的位置。

那么我们能不能反过来想，在 nums[0..sortedIndex-1] 这个部分有序的数组中，找到 nums[sortedIndex] 应该插入的位置，然后进行插入呢？

我想利用数组的有序性：既然 nums[0..sortedIndex-1] 这部分是已经排好序的，那么我就可以用二分搜索来寻找 nums[sortedIndex] 应该插入的位置。

用二分搜索好像是多此一举的。因为就算我用二分搜索找到了 nums[sortedIndex] 应该插入的位置，我还是需要搬移元素进行插入，那还不如一边遍历一遍交换元素的方法简单高效呢。

算法

1. 从 nums[1..n] 开始遍历，对于 nums[sortedIndex]，在 nums[0..sortedIndex-1] 中找到 nums[sortedIndex] 应该插入的位置 j，并一步步左移 nums[sortedIndex] 到 nums[j]的位置
2. 重复步骤 1，直到 nums[sortedIndex] 到达 nums[n]。

代码实现

# 对选择排序进一步优化，向左侧有序数组中插入元素
# 这个算法有另一个名字，叫做插入排序
def sort(nums):
    n = len(nums)
    # 维护 [0, sorted_index) 是有序数组
    sorted_index = 0
    while sorted_index < n:
        # 将 nums[sorted_index] 插入到有序数组 [0, sorted_index) 中
        for i in range(sorted_index, 0, -1):
            if nums[i] < nums[i - 1]:
                # swap(nums[i], nums[i - 1])
                tmp = nums[i]
                nums[i] = nums[i - 1]
                nums[i - 1] = tmp
            else:
                break
        sorted_index += 1

这个算法的名字叫做插入排序，它的执行过程就像是打扑克牌时，将新抓到的牌插入到手中已经排好序的牌中。

初始有序度越高，效率越高

插入排序的空间复杂度是$O(1)$，是原地排序算法。时间复杂度是$O(n^2)$ ，具体的操作次数和选择排序类似，是一个等差数列求和，大约是 $ n^2/2 $次。

如果输入数组已经有序，或者仅有个别元素逆序，那么插入排序的内层 for 循环几乎不需要执行元素交换，所以时间复杂度接近$O(n)$ 。