파이썬 알고리즘

삽입 정렬의 기본 개념: 이미 정렬된 데이터 시퀀스가 ​​있으며, 이미 정렬된 데이터 시퀀스에 숫자를 삽입해야 하지만, 이 경우 삽입 후에도 데이터 시퀀스가 ​​계속 정렬되어야 합니다. , 숫자가 필요합니다. 삽입 정렬 방법 삽입 정렬의 기본 작업은 정렬된 데이터에 데이터를 삽입하여 숫자에 1을 더한 새로운 정렬 데이터를 얻는 것입니다. 작은 양의 데이터를 정렬하는 시간복잡도는 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__ == &#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))