python实现直接插入排序

# 从待排序的n个记录中的第二个记录开始，依次与前面的记录比较并寻找插入的位置，每次外循环结束后，将当前的数插入到合适的位置。
# 时间复杂度: O(n)~O(n^2)

def insert_sort1(array):
    n = len(array)
    for i in range(1, n):
        for j in range(i, 0, -1):
            if array[j] < array[j-1]:
                array[j], array[j-1] = array[j-1], array[j]
            else:
                break

def insert_sort2(array):
    for i in range(1, len(array)):
        if array[i-1] > array[i]:
            index, temp = i, array[i]
            while index > 0 and array[index-1] > temp:
                array[index] = array[index - 1]
                index -= 1
            array[index] = temp
      return array

L = [99, 12, 23, 54, 32, 11, 76, 5, 73, 2, 89, 76, 554, 65, 234]
insert_sort2(L)
>>> [2, 5, 11, 12, 23, 32, 54, 65, 73, 76, 76, 89, 99, 234, 554]