python算法 – 插入排序算法

插入排序的基本概念：有一个已经有序的数据序列，要求在这个已经排好的数据序列中插入一个数，但要求插入后此数据序列仍然有序，这个时候就要用到一种新的排序方法——插入排序法,插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，时间复杂度为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__ == '__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))

• 初学者学习python2还是python3？
• python获取本机IP、mac地址、计算机名
• 详解python2 和 python3的区别
• python基础之删除文件及删除目录的方法
• 用python求第1000个质数的值
• python常用函数年初大总结
• Python3 - 时间处理与定时任务
• Python开发的CMS系统，Silva CMS 3 发布
• python基础之使用os.system来执行系统命令
• 判断python字典中key是否存在的两种方法

• 初学者学习python2还是python3？
• python基础之删除文件及删除目录的方法
• python获取本机IP、mac地址、计算机名
• python获取系统时间（时间函数详解）
• 详解python2 和 python3的区别
• 用python求第1000个质数的值
• Python3 - 时间处理与定时任务
• 命令行看糗百
• Python算法之---冒泡，选择，插入排序算法
• python 中求和函数 sum详解

• range方法在Python2和Python3中的不同
• python3 数组(列表)初始化
• 记一次crontab中date命令错用导致的问题
• MySQL用LIKE特殊字符搜索
• CentOS 7 下修改主机名
• Python3正则表达式之：(?(id/name)y...
• TIOBE编程语言排行榜2019年 Python稳居前三
• 解压命令unzip常用方法汇总
• 解析redis备份文件rdb的两种方法及对比
• 百度视觉语义化平台2.0：交互升级和...
• 5G时代的视觉语义化技术：软硬结合...
• 百度AutoDL重磅升级至3.0：设计、迁...