gpt4 book ai didi

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

转载 作者:qq735679552 更新时间:2022-09-29 22:32:09 26 4
gpt4 key购买 nike

CFSDN坚持开源创造价值,我们致力于搭建一个资源共享平台,让每一个IT人在这里找到属于你的精彩世界.

这篇CFSDN的博客文章浅谈插入排序算法在Python程序中的实现及简单改进由作者收集整理,如果你对这篇文章有兴趣,记得点赞哟.

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

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#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

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

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

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

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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应该存放的位置,而此时移动也随之完成。 代码实现如下:

?
1
2
3
4
5
6
7
8
9
10
11
12
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程序中的实现及简单改进的内容请搜索CFSDN的文章或继续浏览相关文章,希望大家以后支持我的博客! 。

26 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com