打开《Python入门与实战》_一步步学会Python_5.2.5 排序与查找算法

【摘要】 本书摘自《Python入门与实战》一书中第5章，第2节，由王跃进主编。

5.2.5 排序与查找算法

有一个猜数游戏：甲先想好一个小于1000的自然数，乙的任务是猜出这个数。乙 每猜一个数，甲会说“大了”“小了”或“正确”。如果你是乙，你能保证在十次之内 猜中吗?

将一组数据按从小到大(或从大到小)的顺序排列就称为排序，实现排序的方法 就称为排序算法。虽然 Python已经为我们提供了sort()方法用于排序，但是排序方法 是如何工作的呢?下面介绍几种经典的排序算法和二分查找法。

假设列表li=[33,11,23,67,46,2], 现要求将列表变为li=[2,11,23,33,46,67]。

1. 冒泡排序

算法分析：依次比较相邻的两个数，将小数放在前面，大数放在后面。

第一趟：首先比较第1个和第2个数，将小数放前，大数放后。然后比较第2个 数和第3个数，将小数放前，大数放后，以此类推，直到比较最后两个数，将小数放 前，大数放后。最后一个数为最大数。

第二趟：首先比较第1个和第2个数，将小数放前，大数放后。然后比较第2数和第3个数，将小数放前，大数放后，以此类推，直到比较除最后一个数外的两个 数，将小数放前，大数放后。

重复以上过程，直到最后一趟只比较第1个和第2个数时为止。

实现代码：

01 def bubble sort(li):

02 """冒泡排序算法"""

03 n=len(li)- 1

04 for i in range(n):

05 for j in range(n-i):

06 if li[j]>li[j+1]:

07 li[j],li[j+1]= li[j+1],li[j] #交换两个数

08 li =[33,11,23,67,46,2]

09 bubble sort(li)

10 print(li)

第一趟结果： li=[11,23,33,46,2,67]

第二趟结果： li=[11,23,33,2,46,67]

第三趟结果： li=[11,23,2,33,46,67]

第四趟结果： li=[11,2,23,33,46,67]

第五趟结果： li=[2,11,23,33,46,67]

2. 选择排序

算法分析：首先比较第1个和第2个数，将小数放前，大数放后，然后比较第1 个数和第3个数，将小数放前，大数放后，如此继续，直至比较第1个数和最后1个 数为止。得到最小的一个元素，存放在第一个位置。然后用第2个数与后面的所有数 比较，得到第二小的元素，存放到第二个位置，重复这个步骤，直到全部待排序的数 据元素排完。即第一趟找到最小(最大)元素放到第1个位置，第二趟找到第二小(大) 的元素放到第2个位置， ……

实现代码：

def select sort(li):

"""选择排序算法"""

n=len(li)

fori in ng)

for j in range(i+1,n):

if li [i]>li[j]:

li[i],li[j]=li[j],li[i]

li=[33,11,23,67,46,2]

09 select sort(li)

10 print(li)

第一趟结果： li=[2,33,23,46,67,11]

第二趟结果： li=[2,11,23,46,67,33]

第三趟结果： li=[2,11,23,46,67,33]

第四趟结果： li=[2,11,23,33,67,46]

第五趟结果： li=[2,11,23,33,46,67]

在每次比较时，如果前面的数大于后面的数，则交换，我们可以修改为不交换， 只记录位置，待一趟比较完成后，再交换，这样每一趟只交换1次，可以缩短运行时 间，请你试试怎样修改代码?

3. 插入排序

算法分析：第一趟比较第2个元素和第1个元素，将小数放前，大数放后；第二 趟比较第3个元素和第2元素，将小数放前，大数放后，再比较第2个元素和第1元 素，将小数放前，大数放后；第三趟比较第4个元素和第3个元素，将小数放前，大 数放后，再比较第3个元素和第2元素，将小数放前，大数放后，再比较第2个元素 和第1元素，将小数放前，大数放后。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们 18664393530@aliyun.com 处理，核实后本网站将在24小时内删除侵权内容。