03.Array-Insertion-Sort.md

1. 插入排序算法思想

插入排序（Insertion Sort）基本思想：

将整个序列分为两部分：前面 i 个元素为有序序列，后面 n - i 个元素为无序序列。每一次排序，将无序序列的第 1 个元素，在有序序列中找到相应的位置并插入。

简单来说，「插入排序算法」是在每一趟排序中，将无序序列的第 1 个元素，插入到有序序列的适当位置上。

2. 插入排序算法步骤

1. 第 1 趟排序：

   1. 第 1 个元素为有序序列，后面第 2 ~ n 个元素（总共 n - 1 个元素）为无序序列。
   2. 从右至左遍历有序序列中的元素，如果遇到「有序序列的元素 > 无序序列的第 1 个元素」的情况时，则将向有序序列的元素后移动一位。
   3. 如果遇到「有序序列的元素 <= 无序序列的第 1 个元素」的情况或者「到达数组开始位置」时，则说明找到了插入位置。将「无序序列的第 1 个元素」插入该位置。

2. 第 2 趟排序：

   1. 第 1 ~ 2 个元素为有序序列，后面第 3 ~ n 个元素（总共 n - 2 个元素）为无序序列。
   2. 从右至左遍历有序序列中的元素，如果遇到「有序序列的元素 > 无序序列的第 1 个元素」的情况时，则将向有序序列的元素后移动一位。
   3. 如果遇到「有序序列的元素 <= 无序序列的第 1 个元素」的情况或者「到达数组开始位置」时，则说明找到了插入位置。将「无序序列的第 1 个元素」插入该位置。

3. 依次类推，对剩余 n - 3 个元素重复上述排序过程，直到所有元素都变为有序序列，则排序结束。

简单来说，插入排序的算法步骤为：

1. 先将第 1 个元素作为一个有序序列，将第 2 ~ n 个元素作为无序序列。
2. 从左到右遍历一遍无序序列，对于无序序列中的每一个元素：
   1. 遍历有序序列，找到适当的插入位置。
   2. 将有序序列中插入位置右侧的元素依次右移一位。
   3. 将该元素插入到适当位置。

3. 插入排序动画演示

1. 初始序列为：[6, 2, 3, 5, 1, 4]。
2. 第 1 趟排序，将 [6] 作为有序序列，把 [2, 3, 5, 1, 4] 作为无序序列。无序序列第 1 个元素为 2。
   1. 从右向左遍历有序序列 [6]，遇到 6 > 2，则将 6 向右移动 1 位，到达数组开始位置，则找到了合适的插入位置，将 2 插入该位置。
   2. 此时序列变为 [2, 6, 3, 5, 1, 4]。
3. 第 2 趟排序，把 [2, 6] 作为有序序列， [3, 5, 1, 4] 为无序序列。无序序列第 1 个元素为 3。
   1. 从右向左遍历有序序列 [6]，遇到 6 > 3，则将 6 向右移动 1 位，继续遍历，遇到 2 < 3，则找到了合适的插入位置，将 3 插入该位置。
   2. 此时序列变为 [2, 3, 6, 5, 1, 4]。
4. 依次类推，对无序序列中剩余 3 个元素重复上述排序过程，直到无序序列中所有元素都插入到有序序列，则排序结束。此时，序列变为 [1, 2, 3, 4, 5, 6]。

4. 插入排序算法分析

• 最佳时间复杂度：$O(n)$。最好的情况下（初始时序列已经是升序排列），对应的每个 i 值只进行一次元素之间的比较，因而总的比较次数最少，为 $∑^n_{i = 2}1 = n − 1$，并不需要移动元素（记录），这是最好的情况。
• 最差时间复杂度：$O(n^2)$。最差的情况下（初始时序列已经是降序排列），对应的每个 i 值都要进行 i - 1 次元素之间的比较，总的元素之间的比较次数达到最大值，为 $∑^n_{i=2}(i − 1) = \frac{n(n−1)}{2}$。
• 平均时间复杂度：$O(n^2)$。如果序列的初始情况是随机的，即参加排序的序列中元素可能出现的各种排列的概率相同，则可取上述最小值和最大值的平均值作为插入排序时所进行的元素之间的比较次数，约为 $\frac{n^2}{4}$。由此得知，插入排序算法的时间复杂度 $O(n^2)$。
• 排序稳定性：插入排序方法是一种 稳定排序算法。

5. 插入排序代码实现

class Solution:
    def insertionSort(self, arr):
        # 遍历无序序列
        for i in range(1, len(arr)):
            temp = arr[i]
            j = i
            # 从右至左遍历有序序列
            while j > 0 and arr[j - 1] > temp:
                # 将有序序列中插入位置右侧的元素依次右移一位
                arr[j] = arr[j - 1]
                j -= 1
            # 将该元素插入到适当位置
            arr[j] = temp

        return arr

    def sortArray(self, nums: List[int]) -> List[int]:
        return self.insertionSort(nums)