算法思想

直接插入排序是一种简单的插入排序法，其基本思想是：把待排序的纪录（这里我们记为key）的大小逐个插入到一个已经排好序的有序序列中，直到所有的纪录插入完为止，得到一个新的有序序列。

实现

1
2
3
4
5
6
7
8
9
10
11
def InsertionSort(arr):
    for i in xrange(1,len(arr)):
        key = arr[i]

        j = i-1
        while j >= 0 and arr[j] > key:
            arr[j+1] = arr[j]
            j -= 1
        arr[j+1] = key

    return arr

备注：算法实现参照《算法导论》中的内容，注意书中伪码的边界值处理和具体实现的区别。

arr：待排序数组。
key：待比较元素，arr[i]。
arr[0…i-1]：已经排好序的数组。
j：已经排好序的数组的索引。
时间复杂度：O(n^2)