算法原理

将数组看作左右两个部分，保持数组左边有序，将右边的每个数字依次插入到左边的相应位置。

算法实现

def insertion_sort(unsorted_array):
    for i in range(len(unsorted_array)):
        for j in range(i, 0, -1):
            if unsorted_array[j-1] > unsorted_array[j]:
                unsorted_array[j-1], unsorted_array[j] = unsorted_array[j], unsorted_array[j-1]
            else:
                break

上述实现中，对数组第i位的元素不断向前交换，直到无法继续向前交换，此时第i位之前的数组有序。

算法优化

上述算法实现中进行交换操作导致开销很大。其实可以使用右移操作代替交换操作，首先记下第i位的值，将左边的数组逐个右移，直到找到合适的位置，将之前记下的值放入即可。

def insertion_sort_optimization(unsorted_array):
    for i in range(len(unsorted_array)):
        tmp = unsorted_array[i] #记下第i位的值
        is_arranged = False
        for j in range(i, 0, -1):
            if unsorted_array[j-1] > tmp:
                unsorted_array[j] = unsorted_array[j-1] #右移
            else:
                is_arranged = True
                unsorted_array[j] = tmp #把值放入合适的位置
                break
        if not is_arranged:
            unsorted_array[0] = tmp

由于内层循环序列range(i,0,-1)的最小值为1，导致无法把数字放到数组的首位，因此需要进行额外的判断，如果取出的数字在完成内层循环后没有被放入任何位置，说明只能放在数组首位。

上述优化通过进行位置移动来代替交换操作，有效降低了赋值语句的执行次数。

算法测试

对插入排序算法及同为$ O(N^2) $复杂度的选择排序算法进行了正确性及性能测试，以下是测试结果。

创建测试数组

对于插入排序：
1000大小数组耗时:0.047142s
10000大小数组耗时:4.579244s
1000大小随机范围较小数组耗时:0.030886s
1000大小近乎有序数组耗时:0.009190s
.
对于优化后的插入排序：
1000大小数组耗时:0.035747s
10000大小数组耗时:3.236195s
1000大小随机范围较小数组耗时:0.023929s
1000大小近乎有序数组耗时:0.007998s
.
对于选择排序：
1000大小数组耗时:0.036213s
10000大小数组耗时:3.242478s
1000大小随机范围较小数组耗时:0.030851s
1000大小近乎有序数组耗时:0.027903s
.
对于优化后的选择排序：
1000大小数组耗时:0.029559s
10000大小数组耗时:2.578856s
1000大小随机范围较小数组耗时:0.023379s
1000大小近乎有序数组耗时:0.023745s
.
----------------------------------------------------------------------
Ran 4 tests in 14.045s

OK

将上述数据制成表格：

数据量 特点 插入排序 优化后的插入排序 选择排序 优化后的选择排序
1000 随机[0-1000] 0.047142s 0.035747s 0.036213s 0.029559s
10000 随机[0-10000] 4.579244s 3.236195s 3.242478s 2.578856s
1000 随机[0-3] 0.030886s 0.023929s 0.030851s 0.023379s
1000 近乎有序 0.009190s 0.007998s 0.027903s 0.023745s

对这两种排序算法进行比较，可以注意到两种算法的时间开销在同一级别，选择排序在标准测试中拥有稍好的性能。

但值得注意的是，插入排序对于近乎有序的数组有着明显的性能优势，这是由于插入排序是将第i位的数字向前交换，如果数组近乎有序，交换的次数将会很少，从而节约大量时间。

算法复杂度

插入排序需要使用两层循环遍历，因此时间复杂度为$ O(N^2) $，未使用额外空间，空间复杂度为$ O(1) $。对于插入算法的优化仅减少了赋值操作的次数，没有改变算法的整体结构，因此时间复杂度为$ O(N^2) $，空间复杂度为$ O(1) $。