算法实现

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) = 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) = (c_1+c_2+c_4+c_5+c_8)n-(c_2+c_4+c_5+c_8) $$
我们可以把运行时间表示为：
$$ an+b $$

最长运行时间

若输入数组已反向排序，则导致最坏情况
$$ 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) $$
我们可以把运行时间表示为：
$$ an^2+bn+c $$
我们往往集中于只求最坏情况运行时间，即对规模为n的任何输入，算法的最长运行时间。

总结

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