03.Array-Insertion-Sort.md

1. 插入排序算法思想

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

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

可以简述为：每一趟排序中，将剩余无序序列的第一个元素，插入到有序序列的适当位置上。

2. 插入排序算法步骤

• 将第一个元素作为一个有序序列，将第 2 ~ n - 1 个元素作为无序序列。
• 从头至尾一次扫描无序序列，将扫描到的每个元素插入到有序序列的适当位置上。

3. 插入排序动画演示

4. 插入排序算法分析

• 对于具有 n 个元素的序列，插入排序方法一共要进行 n - 1 趟排序。
• 对于插入排序算法，整个排序过程只需要一个辅助空间 temp。
• 当原始序列是一个按值递增序列（升序）时，对应的每个 i 值只进行一次元素之间的比较，因而总的比较次数最少，为 $∑^n_{i = 2}1 = n − 1$，并不需要移动元素（记录），这是最好的情况。
• 最坏的情况是，序列初始时是一个按值递减序列（逆序），则对应的每个 i 值都要进行 i - 1 次元素之间的比较，总的元素之间的比较次数达到最大值，为 $∑^n_{i=2}(i − 1) = \frac{n(n−1)}{2}$。
• 如果序列的初始情况是随机的，即参加排序的序列中元素可能出现的各种排列的概率相同，则可取上述最小值和最大值的平均值作为插入排序时所进行的元素之间的比较次数，约为 $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)