首页 编程教程正文

浅谈插入排序算法在Python程序中的实现及简单改进

piaodoo 编程教程 2020-02-02 12:37:31 905 0 python教程

这篇文章主要介绍了插入排序算法在Python程序中的实现及简单改进,插入排序算法的最差时间复杂度为O(n^2),最优时间复杂度为O(n),存在一定的优化空间,需要的朋友可以参考下

Python实现插入排序的一般范例为:

#coding=cp936
#coding=cp936
#插入排序算法
def InsertionSort(A):
  for j in range(1,len(A)):
    key = A[j]
    i = j-1
    #向前查找插入位置
    while i>=0 and A[i]>key:
      A[i+1] = A[i]
      i = i-1
    A[i+1] = key
 
#初始化输入数据
A = []
input = raw_input('please input some numbers:') #输入逗号分隔整数列 如:7,6,5,1,8,34
for item in input.split(','):
  A.append(int(item))
 
InsertionSort(A)#插入排序
print A

插入算法的原理是:当前元素和已经排序好的部分比较,满足条件时插入,插入点之后的元素全部往后移。
然而,我也正是受这个描述的误导,在实现的时候走了一些弯路。比如有以下列表:

test = [2, 5, 11, 21, 10, 18, 24]

比如当前元素是10,我在开最初的实现思路是从列表的第一个元素开始,一直比较到元素11才找到合适位置.这样做最终是可以实现排序的,但是有一个问题,就是当我把10插入11的位置之后,11和21都需要往后移,这又需要另一个循环,实现如下:

def insertSort(sort_list):
  list_length = len(sort_list)
  if list_length < 2 :
    return sort_list
  for i in range(1,list_length):
    key = sort_list[i]
    j = 0
    while j < i:
      if sort_list[j] > key:
        for k in range(i,j,-1):
          sort_list[k] = sort_list[k-1]
        sort_list[j] = key
        break
      j += 1
  return sort_list

   首先,引入了三个循环变量以及三层循环,效率较低;其次是代码结构会比较混乱,需要改进。

后来我想能不能比较完一个元素就把它移到合适的位置,好如去超市买水果,手里拿到不合适的,总会直接把它放到一边,不会再碰它。具体到算法实现,还用上面的列表举例,当前元素是10,先跟相邻的21比较,发现21比10大,则21往后移动一位,即移到10所在位置;然后10和11比较,又会把11往后移动一位;在比较到元素5时,发现已经找到了10应该存放的位置,而此时移动也随之完成。
代码实现如下:

def insertSort(sort_list):
  list_length = len(sort_list)
  if list_length < 2 :
    return sort_list
  for i in range(1,list_length):
    key = sort_list[i]
    j = i - 1
    while j >=0 and sort_list[j] > key:
      sort_list[j+1] = sort_list[j]
      j -= 1
    sort_list[j+1] = key
  return sort_list

   孰优孰劣,大家对比便知。

版权声明:

本站所有资源均为站长或网友整理自互联网或站长购买自互联网,站长无法分辨资源版权出自何处,所以不承担任何版权以及其他问题带来的法律责任,如有侵权或者其他问题请联系站长删除!站长QQ754403226 谢谢。

有关影视版权:本站只供百度云网盘资源,版权均属于影片公司所有,请在下载后24小时删除,切勿用于商业用途。本站所有资源信息均从互联网搜索而来,本站不对显示的内容承担责任,如您认为本站页面信息侵犯了您的权益,请附上版权证明邮件告知【754403226@qq.com】,在收到邮件后72小时内删除。本文链接:https://www.piaodoo.com/2696.html

评论

搜索

游戏网站源码,织梦网站源码,wordpress,wordpress主题,wordpress下载,wordpress插件,wordpress.com,wordpress模板,wordpress教程,wordpress 主题,wordpress安装,wordpress 模板,wordpress 插件,wordpress主题下载,wordpress企业主题,wordpress seo,wordpress主题开发,wordpress theme,wordpress论坛,wordpress 企业主题,wordpress主机,wordpress中文主题,wordpress cms主题,wordpress plugin,wordpress 主题下载,wordpress 主机,wordpress空间,wordpress mu,wordpress 模版,wordpress汉化主题,wordpress淘宝客主题,wordpress 空间,wordpress代码,WORDPRESS HOSTING,wordpress优点,wordpress安卓客户端,wordpress技巧,wordpress换空间,wordpress themes,网站模板,ppt模板网站,模板网站,企业网站模板,网站设计模板,免费网站模板,个人网站模板,ppt模板下载网站,网站模板下载,公司网站模板,门户网站模板,学校网站模板,网站首页模板,网站模板免费下载,旅游网站模板,网站后台模板,免费网站模板下载,传奇网站模板,网站建设模板,外贸网站模板,网站 模板,个人主页网站模板,个人网站模板下载,政府网站模板,音乐网站模板,导航网站模板,免费企业网站模板,企业网站模板下载,手表网站模板,韩国网站模板,汽车网站模板,教育网站模板,网站后台管理模板,班级网站模板,新闻网站模板,房产中介网站模板,旅游网站模板下载,工艺品网站模板,电子商务网站模板,旅游网站设计模板,团购网站模板,flash网站模板,个人网站设计模板,婚庆网站模板,广告公司网站模板,商业网站模板,手机网站模板,免费模板网站推荐,ppt免费模板网站推荐,织梦网站模板,html网站模板建站,网站html模板,免费个人网站模板,公司网站源码,sns源码,彩票网站源码,周易网站源码,源码基地,交友源码,学校网站源码,asp.net 源码,源码天下,jsp网站源码,论坛源码下载,广告联盟源码,建站源码,delphi源码,源码爱好者,酷源码,net源码,源码超市,医疗网站源码,flash源码,搜源码,源码程序,dede源码,新闻网站源码,易语言源码大全,旅游网站源码下载,flash 源码,免费源码论坛,android游戏源码,电脑维修网站源码,30源码网,股票软件源码,卖源码,源码教程,安居客 源码,vip源码,家教源码,.net源码下载,Web源码,网络公司源码,佛教网站源码,android源码学习,房产源码,钓鱼网站源码,775源码屋,web游戏源码,成品网站 源码78w78不用下载,h5游戏网站源码,asp网站源码下载,webgame源码,电子商务网站源码,vb.net源码,乐嘿源码,8a商业源码论坛,fbreader源码,在线客服系统 源码,google源码,.net网站源码,快递查询源码,源码搜藏网,dede整站源码,周易 源码,52源码论坛,财经网站源码,织梦下载站源码,qq钓鱼网站源码,flash游戏源码,房产网源码,源码搜搜,电子商务源码,团购网站源码,团购网源码,jsp源码下载,jsp源码,h站源码,8a源码,婚纱摄影网站源码,易语言盗号源码,x站源码,qq空间psd源码,免费商业源码,笑话网站源码,源码集合,源码家园,啊哦源码,星期六源码,源码熊,阿奇源码,百分百源码网,一手日源码资源,旅行网站源码,b站工程源码泄露,新站长源码,8a商业源码,asp论坛源码,flash源码下载,404源码社区,创业网站源码,php网页源码,易支付源码,成品网站w灬源码,免费CMS成品网站源码,成品网站W灬源码1688仙踪林,成品APP短视频源码下载网站,成品网站源码1688可靠吗,免费B2B网站源码,成品APP直播源码下载,国外儿童网站源码在线,成品网站W灬源码1688,源码,成品网站w灬 源码1688,免费源码网站都有哪些,成品网站源码78W78隐藏通道1,网站源码,源码网,源码网站,源码时代,源码之家,源码下载,php源码,易语言源码,源码论坛,源码是什么,商城源码,论坛源码,源码交易,源码站,源码库,免费源码,免费网站ja**源码大全,ja**源码,成品网站w灬源码1377,a5源码,站长源码,成品网站源码78W78隐藏通道1APP,源码分享,网站源码下载,源码中国,asp源码,源码社区,企业网站源码,php源码下载,成品app直播源码搭建,在线观看视频网站源码2021,旅游网站源码,安卓源码,通达信选股公式源码,神马影院php源码,c#源码,成品网站w灬源码1688网页,php 源码,网页游戏源码,android源码下载,源码吧,视频源码大全,成品短视频APP源码搭建,asp源码下载,私服源码,电脑维修源码,个人主页源码,源码出售,php网站源码,刀客源码,网址导航源码,导航网站源码,源码天空,asp 源码,软件源码,精品源码,成品网站源码1688自动跳转,个人网站源码,源码哥,在线考试系统源码,cms源码,c# 源码,商业源码,vb源码,门户网站源码,音乐网站源码,中国源码,安卓源码下载,asp网站源码,在线客服源码,电影网站源码,免费源码下载,整站源码,源码交易网,易语言源码网,.net源码,在线客服系统源码,淘客源码,卡盟源码,网站源码出售,vb源码下载,莎莎源码,熊猫烧香源码,asp.net源码,商业源码网,外贸网站源码,61源码网,zblog模板,zblog企业模板,帝国cms模板,帝国cms插件,discuz模板