Python-Algorithmus

Grundkonzept der Einfügungssortierung: Es gibt eine bereits geordnete Datensequenz und es ist erforderlich, eine Zahl in die bereits angeordnete Datensequenz einzufügen, aber es ist erforderlich, dass die Datensequenz nach dem Einfügen noch geordnet ist Eine neue Sortiermethode ist erforderlich: Die Einfügungssortierung besteht darin, Daten in die sortierten Daten einzufügen, um neue geordnete Daten mit der Zahl plus eins zu erhalten Der Algorithmus eignet sich für Die zeitliche Komplexität beim Sortieren einer kleinen Datenmenge beträgt O(n^2). Es handelt sich um eine stabile Sortiermethode. Der Einfügealgorithmus teilt das zu sortierende Array in zwei Teile: Der erste Teil enthält alle Elemente des Arrays bis auf das letzte Element, und der zweite Teil enthält nur dieses eine Element. Nachdem der erste Teil sortiert ist, fügen Sie das letzte Element an der Position des ersten Teils ein, der jetzt sortiert ist

# -*- 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))