首页 / 操作系统 / Linux / Python实现插入排序

Python实现插入排序一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：
 1.从第一个元素开始，该元素可以认为已经被排序
2.取出下一个元素，在已经排序的元素序列中从后向前扫描
3.如果该元素（已排序）大于新元素，将该元素移到下一位置
4.重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
5.将新元素插入到该位置后
6.重复步骤2~5
 
最优时间复杂度O（n）
 
最差时间复杂度O（n^2）#！ /usr/bin/env python
 # -*- coding: utf-8 -*-
 def insertion_sort（l）:
   length = len（l）
   for i in range（1, length）:
       item = l.pop（i）
       for j in range（i,0,-1）:
           if item >= l[j-1]:
               l.insert（j, item）
               break
       else:
           l.insert（0, item）
 if __name__ == "__main__":
   l1 = [3, 1, 2, 4, 9, 8, 6, 7, 5]
   print l1
   insertion_sort（l1）   
   print l1《Python核心编程 第二版》.（Wesley J. Chun ）.[高清PDF中文版] http://www.linuxidc.com/Linux/2013-06/85425.htm《Python开发技术详解》.（ 周伟,宗杰）.[高清PDF扫描版+随书视频+代码] http://www.linuxidc.com/Linux/2013-11/92693.htmPython脚本获取Linux系统信息 http://www.linuxidc.com/Linux/2013-08/88531.htm在Ubuntu下用Python搭建桌面算法交易研究环境 http://www.linuxidc.com/Linux/2013-11/92534.htmPython 的详细介绍：请点这里
Python 的下载地址：请点这里本文永久更新链接地址：http://www.linuxidc.com/Linux/2014-06/103896.htm