python插入排序算法菜鸟教程

概述python插入排序算法菜鸟教程 对python这个高级语言感兴趣的小伙伴，下面一起跟随内存溢出 jb51.cc的小编两巴掌来看看吧！

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

# @param python算法 - 插入排序算法# @author 内存溢出 jb51.cc|jb51.cc # -*- 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__ == '__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))# End www.jb51.cc

总结

以上是内存溢出为你收集整理的python插入排序算法菜鸟教程全部内容，希望文章能够帮你解决python插入排序算法菜鸟教程所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。