- # -*- coding: 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))
- #该片段来自于http://www.codesnippet.cn/detail/290920136221.html
来源: http://www.codesnippet.cn/detail/290920136221.html