python algorithm

The basic concept of insertion sort: There is an already ordered data sequence, and it is required to insert a number into the already arranged data sequence, but it is required that the data sequence is still ordered after the insertion. At this time, a new method is used The sorting method - insertion sort. The basic operation of insertion sort is to insert a data into the ordered data that has been sorted, so as to obtain a new ordered data with the number plus one. The algorithm is suitable for a small amount of data. The time complexity of sorting is O(n^2). It is a stable sorting method. The insertion algorithm divides the array to be sorted into two parts: the first part contains all the elements of the array except the last element, and the second part contains only this one element. After the first part is sorted, insert the last element into the position of the first part that is now sorted

# -*- encoding: utf-8 -*-
  
def insertion_sort(iterable, cmp=cmp):
    """插入排序，伪码如下：
    INSERTION-SORT(A)
    1  for j ← 2 to length[A] // 从第二个数开始
    2    do key ← A[j] // 该数作为待排序的数
    3      ▷ Insert A[j] into the sorted sequence A[1..j-1]. // 将key插入已排序子数组
    4      i ← j-1 // key前一位索引
    5      while i > 0 and A[i] > key // 前一位存在且大于key时
    6        do A[i+1] ← A[i] // 后移一位
    7           i ← i-1 // 索引再向前一位
    8      A[i+1] ← key // 直到前一位不存在或<=key了，key插入
  
    T(n) = θ(n^2)
  
    Args:
        iterable (Iterator): 可迭代对象。
        cmp (Function): 比较函数。默认为内建函数cmp()。
  
    Returns:
        一个排序后的列表。
    """
    if (iterable == None):
        return None
    lst = [] # 结果列表
    length = len(iterable)
  
    for key in iterable:
        i = len(lst) # 列表长度
        # 从末尾往前与key比较，直到不大于key
        while i > 0 and cmp(lst[i-1], key) > 0:
            i = i - 1
        lst.insert(i, key); # i处插入key
  
    return lst
  
if __name__ == &#39;__main__&#39;:
    import random, timeit
  
    items = range(10000)
    random.shuffle(items)
  
    def test_sorted():
        print(items)
        sorted_items = sorted(items)
        print(sorted_items)
  
    def test_insertion_sort():
        print(items)
        sorted_items = insertion_sort(items)
        print(sorted_items)
  
    test_methods = [test_sorted, test_insertion_sort]
    for test in test_methods:
        name = test.__name__ # test.func_name
        t = timeit.Timer(name + &#39;()&#39;, &#39;from __main__ import &#39; + name)
        print(name + &#39; takes time : %f&#39; % t.timeit(1))