python算法 - 插入排序算法-Toy模板网

这篇具有很好参考价值的文章主要介绍了python算法 - 插入排序算法。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

插入排序的基本概念：有一个已经有序的数据序列，要求在这个已经排好的数据序列中插入一个数，但要求插入后此数据序列仍然有序，这个时候就要用到一种新的排序方法——插入排序法,插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，时间复杂度为O(n^2)。是稳定的排序方法。插入算法把要排序的数组分成两部分：第一部分包含了这个数组的所有元素，但将最后一个元素除外，而第二部分就只包含这一个元素。在第一部分排序后，再把这个最后元素插入到此刻已是有序的第一部分里的位置文章来源地址https://www.toymoban.com/news/detail-518102.html

# -*- 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 keyin 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 testin test_methods:
        name= test.__name__# test.func_name
        t= timeit.Timer(name+ '()','from __main__ import ' + name)
        print(name+ ' takes time : %f' % t.timeit(1))

到了这里，关于python算法 - 插入排序算法的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！