算法实现

1
2
3
4
5
6
7
8
9
def insertion_sort(vector):
    for j in range(1,len(vector)):
        key = vector[j]
        i = j - 1
        while i >= 0 and vector[i] > key:
            vector[i + 1] = vector[i]
            i -= 1
        vector[i + 1] = key
    return vector

算法分析

运行时间

T(n)=c1n+c2(n−1)+c4(n−1)+c5∑j=2ntj+c6∑j=2n(tj−1)+c7∑j=2n(tj−1)+c8(n−1) T(n) = c_1n+c_2(n-1)+c_4(n-1)+c_5\sum_{j=2}^n t_j + c_6\sum_{j=2}^n (t_j -1) + c_7\sum_{j=2}^n (t_j -1) + c_8(n-1)

最佳运行时间

若输入数组已排好序，则出现最佳情况
T(n)=(c1+c2+c4+c5+c8)n−(c2+c4+c5+c8) T(n) = (c_1+c_2+c_4+c_5+c_8)n-(c_2+c_4+c_5+c_8)
我们可以把运行时间表示为：
an+b an+b

最长运行时间

若输入数组已反向排序，则导致最坏情况
T(n)=(c52+c62+c72)n2+(c1+c2+c4+c52−c62−c72+c8)n−(c2+c4+c5+c8) T(n) = (\frac{c_5}{2} + \frac{c_6}{2} + \frac{c_7}{2})n^2 + (c_1+c_2+c_4+\frac{c_5}{2} - \frac{c_6}{2} - \frac{c_7}{2}+c_8)n - (c_2+c_4+c_5+c_8)
我们可以把运行时间表示为：
an2+bn+c an^2+bn+c
我们往往集中于只求最坏情况运行时间，即对规模为n的任何输入，算法的最长运行时间。

总结

对于少量元素的排序，插入排序是一个有效的算法。