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

yipeiwu_com5年前Python基础

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

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

相关文章

python处理文本文件实现生成指定格式文件的方法

本文所述实例为Python处理文本文件并生成指定格式文件的方法,具体实现功能代码如下所示: import os import sys import string #以指定模式打开指...

简析Python的闭包和装饰器

简析Python的闭包和装饰器

什么是装饰器? 装饰器(Decorator)相对简单,咱们先介绍它:“装饰器的功能是将被装饰的函数当作参数传递给与装饰器对应的函数(名称相同的函数),并返回包装后的被装饰的函数”,听起来...

给我一面国旗 python帮你实现

给我一面国旗 python帮你实现

本文实例为大家分享了Python之给我一面国旗的具体代码,供大家参考,具体内容如下 1、“给我一面国旗@微信官方” 今天“给我一面国旗@微信官方”刷爆了朋友圈,我也蹭波热度,出个Pyth...

Python查找数组中数值和下标相等的元素示例【二分查找】

本文实例讲述了Python查找数组中数值和下标相等的元素。分享给大家供大家参考,具体如下: 题目描述: 假设一个单调递增的数组中的每个元素都是整数并且是唯一的。请编程实现一个函数,找出数...

python采集百度搜索结果带有特定URL的链接代码实例

这篇文章主要介绍了python采集百度搜索结果带有特定URL的链接代码实例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 #cod...