插入排序 python实现

问题描述

【输入】n个数组成的序列 $A_n=[a_1,a_2,\cdot \cdot \cdot ,a_n]$

【输出】$A_n$的一个重新排列$A_n^{\prime }$，使得 $a_1\le a_2\le \cdot \cdot \cdot \le a_n$

算法展示

def insertion_sort(An):
    """插入排序"""
    n = len(An)  # 获取An的长度

    for i in range(1, n):
        key = An[i]  # 当前需要插入排序的值
        j = i - 1  # 左一位的下标
        while j >= 0 and An[j] > key:
            # 向左比较并移动,直到找到自己的位置
            An[j + 1] = An[j]
            j -= 1
        An[j + 1] = key
    return An
1
2
3
4
5
6
7
8
9
10
11
12
13

算法基本分析

加入一系列print语句以辅助分析：

def insertion_sort(An):
    """插入排序"""
    n = len(An)  # 获取An的长度
    print(f"输入:{An}\n")
    for i in range(1, n):
        key = An[i]  # 当前需要插入排序的值

        print(f"-----第{i}次-----")
        print(f"origin:{An[0:i]} {An[i:]}")

        j = i - 1  # 左一位的下标
        while j >= 0 and An[j] > key:
            # 向左比较并移动,直到找到自己的位置
            An[j + 1] = An[j]
            j -= 1
        An[j + 1] = key

        print(f"result:{An[0:i+1]} {An[i+1:]}")
    print(f"\n输出:{An}")
    return An
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

以[6,7,3,4,8,1,2,5]作为输入的$A_n$ ,得到以下结果:

输入:[6, 7, 3, 4, 8, 1, 2, 5]

-----第1次-----
origin:[6] [7, 3, 4, 8, 1, 2, 5]
result:[6, 7] [3, 4, 8, 1, 2, 5]
-----第2次-----
origin:[6, 7] [3, 4, 8, 1, 2, 5]
result:[3, 6, 7] [4, 8, 1, 2, 5]
-----第3次-----
origin:[3, 6, 7] [4, 8, 1, 2, 5]
result:[3, 4, 6, 7] [8, 1, 2, 5]
-----第4次-----
origin:[3, 4, 6, 7] [8, 1, 2, 5]
result:[3, 4, 6, 7, 8] [1, 2, 5]
-----第5次-----
origin:[3, 4, 6, 7, 8] [1, 2, 5]
result:[1, 3, 4, 6, 7, 8] [2, 5]
-----第6次-----
origin:[1, 3, 4, 6, 7, 8] [2, 5]
result:[1, 2, 3, 4, 6, 7, 8] [5]
-----第7次-----
origin:[1, 2, 3, 4, 6, 7, 8] [5]
result:[1, 2, 3, 4, 5, 6, 7, 8] []

输出:[1, 2, 3, 4, 5, 6, 7, 8]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

循环不变式(Loop Invariant)

循环不变式是在每一次循环中都不改变的性质。它有助于我们分析归纳类算法的正确性。

循环不变式的特点:

• 初始化时为真 (初始条件)
• 若单次循环开始时为真，则本次循环结束时也为真 （循环不变条件)
• 整个循环结束后，依旧为真 (结论)

可以对比数学归纳法:

• i=1时,结论成立 (初始条件)
• 若i=n时,结论成立，则i=n+1时,结论也成立 （归纳条件)
• 得证，对任意i,结论均成立 (结论)

对插入排序算法进行分析，

外层循环的循环不变式为
$$\begin{gathered} 第i次循环开始时, \\ 左侧子序列A_n[0:i]已排好序, \\ 即满足a_1<a_2<\cdot \cdot \cdot <a_i \end{gathered}$$

• 初始化时，$A_n[0:1]$ 只有一个数，显然为真
• 假设第i次循环时，$A_n[0:i]$已排好序。此时key=An[i]。经过内层循环的比较与移动，$A_n[0:i]$中大于key的值都在key的右侧，小于等于key的值都在key的左侧。即，$A_n[0:i+1]$这i+1个数也已排好序。
• 得证，经过n-1次循环后，$A_n[0:n]$这n个数已排好序。即，得到了排好序的$A_n^{\prime }$ .

算法复杂度分析

输入规模(Input Size)

输入规模是指算法所接受的输入单位数据的个数。

不同问题的输入单位数据可能是不同的。

插入排序的输入单位数据是列表中的单个数字。

因此，其输入规模n为输入数字列表的元素个数。

运行时间(Running Time)

假设代码的每一步执行需要常数时间$c_i$

记所有代码运行的时间和记为算法的运行时间$T_n$

def insertion_sort(An):
    n = len(An)   #----- c1  1
    for i in range(1, n):  #----- c2  n
        key = An[i]   #----- c3  n-1
        j = i - 1	#----- c4  n-1
        while j >= 0 and An[j] > key:  #----- c5  sum_{i=1}^{n-1} t_i
            An[j + 1] = An[j] #-----c6 sum_{i=1}^{n-1} (t_i-1)
            j -= 1 #-----c7 sum_{i=1}^{n-1} (t_i-1)
        An[j + 1] = key #-----c8 n-1
    return An
1
2
3
4
5
6
7
8
9
10

如果为最佳情况，即输入的$A_n$已经排好了序，则$c_5$步骤只需要执行1次就能退出内层循环

则$\sum _{i=1}^{n-1}{t}_i=\sum _{i=1}^{n-1}1=n-1$ ,$\sum _{i=1}^{n-1}(t_i-1)=\sum _{i=1}^{n-1}0=0$

故执行时间

$T(n)=c_1+c_{2}n+c_3(n-1)+c_4(n-1)+c_5(n-1)+c_8(n-1)$

$=(c_2+c_3+c_4+c_5+c_8)n-(c_3+c_4+c_5+c_8-c_1)$

$=An+B$

如果为最坏情况，即输入的$A_n$为逆序，则$c_5$步骤只需要执行(i+1)次才能退出内层循环

则$\sum _{i=1}^{n-1}{t}_i=\sum _{i=1}^{n-1}(i+1)=\frac{(2+n)(n-1)}{2}=\frac{n^2+n-2}{2}$ ,

$\sum _{i=1}^{n-1}(t_i-1)=\sum _{i=1}^{n-1}i=\frac{n(n-1)}{2}=\frac{n^2-n}{2}$

故执行时间

$T(n)=c_1+c_{2}n+c_3(n-1)+c_4(n-1)+c_5(\frac{n^2+n-2}{2})+c_6(\frac{n^2-n}{2})+c_7(\frac{n^2-n}{2})+c_8(n-1)$

$=\frac{c_5+c_6+c_7}{2}{n}^2+(\frac{c_5-c_6-c_7}{2}+c_2+c_3+c_4+c_8)n+(c_1-c_3-c_4-c_5-c_8)$

$=A{n}^2+Bn+C$

设算法的执行时间为$T(n)$,则大O表示法----$O(f(n))$代表$T(n)$的上界的量级，大$\Omega$ 表示法----$\Omega (f(n))$代表$T(n)$的下界的量级。

如表示插入排序的执行时间: $O(n^2)$ , $\Omega (n)$

常用大O表示法分析算法的时间复杂度。

由上述分析，

插入排序的时间复杂度为$O(n^2)$.