插入排序的基本概念：有一個(gè)已經(jīng)有序的數(shù)據(jù)序列，要求在這個(gè)已經(jīng)排好的數(shù)據(jù)序列中插入一個(gè)數(shù)，但要求插入后此數(shù)據(jù)序列仍然有序，這個(gè)時(shí)候就要用到一種新的 排序方法——插入排序法,插入排序的基本操作就是將一個(gè)數(shù)據(jù)插入到已經(jīng)排好序的有序數(shù)據(jù)中，從而得到一個(gè)新的、個(gè)數(shù)加一的有序數(shù)據(jù)，算法適用于少量數(shù)據(jù)的 排序，時(shí)間復(fù)雜度為O(n^2)。是穩(wěn)定的排序方法。插入算法把要排序的數(shù)組分成兩部分：第一部分包含了這個(gè)數(shù)組的所有元素，但將最后一個(gè)元素除外，而第 二部分就只包含這一個(gè)元素。在第一部分排序后，再把這個(gè)最后元素插入到此刻已是有序的第一部分里的位置

# -*- encoding: utf-8 -*-
  
def insertion_sort(iterable, cmp=cmp):
    """插入排序，偽碼如下：
    INSERTION-SORT(A)
    1  for j ← 2 to length[A] // 從第二個(gè)數(shù)開始
    2    do key ← A[j] // 該數(shù)作為待排序的數(shù)
    3      ? Insert A[j] into the sorted sequence A[1..j-1]. // 將key插入已排序子數(shù)組
    4      i ← j-1 // key前一位索引
    5      while i > 0 and A[i] > key // 前一位存在且大于key時(shí)
    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): 比較函數(shù)。默認(rèn)為內(nèi)建函數(shù)cmp()。
  
    Returns:
        一個(gè)排序后的列表。
    """
    if (iterable == None):
        return None
    lst = [] # 結(jié)果列表
    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))

標(biāo)簽：

版權(quán)申明：本站文章部分自網(wǎng)絡(luò)，如有侵權(quán)，請聯(lián)系：west999com@outlook.com
特別注意：本站所有轉(zhuǎn)載文章言論不代表本站觀點(diǎn)！
本站所提供的圖片等素材，版權(quán)歸原作者所有，如需使用，請與原作者聯(lián)系。