插入排序（Insertion Sort）

一、基本思想

插入排序的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入.插入排序在实现上,通常采用in-place排序（即只需用到O(1)的额外空间的排序）,因而在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间.

二、实现逻辑

有一组数字：｛5, 2, 4, 6, 1, 3｝,Arrange the group of numbers from smallest to largest.从第二个数字开始,Think of it as a newly added number,The second number just needs to be sorted by comparing it with the first number to the left;in the third number,Consider the first two sorted numbers to be the sorted cards in your hand,Then just compare the third number with the first two numbers;以此类推,Until the last number is compared with all previous numbers,插入排序完成.

算法步骤：

1. 从第一个元素开始,该元素可以认为已经被排序;
2. 取出下一个元素,在已经排序的序列中从后向前扫描;
3. If an element in the sorted sequence is greater than the new element,则将该元素移到下一位置;
4. 重复步骤 3,直到找到已排序的元素小于或等于新元素的位置;
5. 将新元素插入到该位置;
6. 重复步骤 2 ~ 5.

三、时间复杂度的分析

If the goal of insertion sort is to put $n$ Sort a sequence of elements in ascending order,那么：

• If the sequence is already in ascending order,只需要比较 $n-1$ 次即可,That is, the best time complexity is ：$\Omega (n)$;
• If the sequence is in descending order,Then since the sequence has at most $n(n-1)/2$ pair reverse order,即最坏时间复杂度为：$O(n^2)$.

For the average time complexity,长度为 $n$ 的序列有 $n!$ 种排列,Therefore, the permutation of each sequence is average $n(n-1)/4$ pair reverse order,Therefore, the average time complexity is ：$\Theta (n^2)$.

四、空间复杂度的分析

Because the algorithm uses isin-place排序方法,No additional openings will be made $O(n)$ 的数组空间（out-place排序）,所以空间复杂度为：$O(1)$.

五、算法实现

直接插入

def insertion_sort(array: List) -> None:
	''' 支持数值型数据,如整型与浮点型混合;支持全为字符串类型的数据;不支持字符串型与数值型混合. '''
    for index in range(1, len(array)):
        key = array[index]
        pre = index - 1
        while pre >= 0 and key < array[pre]:
            array[pre + 1] = array[pre]
            pre -= 1
        array[pre + 1] = key

折半插入

def insertion_sort(array: List) -> None:
	''' 支持数值型数据,如整型与浮点型混合;支持全为字符串类型的数据;不支持字符串型与数值型混合. '''
    for index in range(1, len(array)):
        key = array[index]
        low, high = 0, index - 1
        while low <= high: # A sequence that conforms to monotonicity
            mid = (low + high) // 2
            if key > array[mid]:
                low = mid + 1
            else:
                high = mid - 1
        for pre in range(index, low, -1): # 从后往前
            array[pre] = array[pre - 1]
        array[low] = key