插入排序的根基观念：有一个已经有序的数据序列，要求在这个已经排好的数据序列中插入一个数，但要求插入后此数据序列仍然有序，这个时候就要用到一种新的排序要领——插入排序法,插入排序的根基操纵就是将一个数据插入到已经排好序的有序数据中，从而获得一个新的、个数加一的有序数据，算法合用于少量数据的排序，时间巨大度为O(n^2)。是不变的排序要领。插入算法把要排序的数组分成两部门：第一部门包括了这个数组的所有元素，但将最后一个元素除外，而第二部门就只包括这一个元素。在第一部门排序后，再把这个最后元素插入到而今已是有序的第一部门里的位置
# -*- 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__ == '__main__':
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 + '()', 'from __main__ import ' + name)
print(name + ' takes time : %f' % t.timeit(1))
