插入排序

Python代码

def insertionSort(numbers) : 
    length = len(numbers)
    if length > 1:
        i = 1
        for i in range(length):
            key = numbers[i]
            j = i - 1
            while j >= 0 and numbers[j] > key :
                numbers[j + 1] = numbers[j]
                j = j - 1
            numbers[j + 1] = key

输入：[6, 1, 3, 4, 2, 5]
输出：[1, 2, 3, 4, 5, 6]

最好情况：an+b
最坏情况：an^2+bn+c
（a、b、c都是依赖于代价c的常量）