31 - 冒泡排序之畅销书排行榜

鱼C-小师妹

在线讲解：



上学时我们都有过这种经历吧。

课间操开始前，各个年级的同学走到操场上，高低不齐，杂乱无序。

然后在班长指挥下，按照高个在后，排成一列，很快操场上就会非常整齐有序。

在编程中有一个算法也是使用类似的排序规则：冒泡排序。

顾名思义，排序过程中较小或较大的元素会像气泡一样不断上浮。

冒泡排序算法的基本思想：

从第一个数开始，依次比较相邻的两个数，将小数放在前面，大数放在后面，经过一轮比较后，最大的数将位于最后一个位置。然后继续从第一个数开始，依次比较相邻数，直到将倒数第二大的数置于倒数第二位置。如此重复，直到所有数都完成排序。这个过程就好像一个个气泡逐渐从水底浮到了水面上。

同样，也可以按从大到小的顺序排列。

我们举个例子假设初始值：4，9，1，6，3，5

第一次排序

未排序区域：4，9，1，6，3，5

先用 4 和 9 比较，因为 4 小于 9，所以不用交换。

再用第二个位置的 9 和第三个位置的 1 比较，因为 9 大于 1，交换：4，1，9，6，3，5

接着比较，后面同理由于 9 大于接下来的几个值，完成第一轮排序后结果：4，1，6，3，5，9

经过第一次排序，最大值 9 被放在了最后的位置。

因此在第二次排序时，只需要从第一个数开始，比较到倒数第二个数，也就是 5 即可。

第二次排序

未排序区域：4，1，6，3，5

依旧从第一个位置开始，4 大于 1，交换。4 小于 6，不交换：1，4，6，3，5

再从 6 开始与 3 比较，大于，交换：1，4，3，6，5

最后 6 大于 5 交换：1，4，3，5，6

经过第二次排序，已经将新数列 4，1，6，3，5 中的最大值 6，也就是原数列的第二大值，放在了倒数第二的位置。

因此，在进行第三次排序时，只需要从第一个数开始，比较到倒数第三个数，也就是 5 即可。

第三次排序

未排序区域：1，4，3，5

还是从第一位开始，1 小于 4，用 4 和 3 比较，大于，交换：1，3，4，5

4 小于 5，不交换：1，3，4，5

经过第三次排序，已经将新数列 1，4，3，5 中的最大值 5，也就是原数列的第三大值，放在了倒数第三的位置。

因此，在进行第四次排序时，只需要从第一个数开始，比较到 4 即可。

第四次排序

未排序区域：1，3，4

依旧从第一位开始，1 小于 3，3 小于 4

经过第四次排序，已经将新数列 1，3，4 中的最大值 4，也就是原数列的第四大值，放在了倒数第四的位置。

因此，在进行第五次排序时，只需要从第一个数开始，比较到 3 即可。

第五次排序。

未排序区域：1，3

依然从第一个位置开始比较，1 小于 3，不交换位置。

因为只有两个数，第五次排序完成。

第六次排序

未排序区域：1

此时只剩 1，完成排序：1，3，4，5，6，9

接下来我们用代码实现上述过程。

先来创建列表存储初始值，并打印：

data = [4,9,1,6,3,5]
print("原列表：",data) 

然后就是调用我们上面的冒泡排序算法，这里就叫 bubble：

print('\n----我是分界线------\n')
bubble(data)
print('\n----我是分界线------')

接下来就是关键，实现 bubble：

通过上面的逐步演示可知排序次数就是列表长度。

因为 for 循环从 0 开始，所以遍历开始位置就是 len(data)-1。

最终是 6 次，所以结束位置是 -1，每一轮 i 减 1，写成代码：

    for i in range(len(data)-1,-1,-1):

每一轮的比较都比较上一轮少，所以 j 直接遍历到 i 即可：

        for j in range(i):

如果数据小于原来的数据就交换位置：

            if data[j+1] < data[j]:
                data[j],data[j+1] = data[j+1],data[j]

好啦，这就实现了冒泡排序的核心部分。

接下来我们实现打印功能：

print(f"第{len(data)-i}次排序后：",end='')
        for j in range(len(data)):
            print(data[j],end=' ')
        print()

结果：



源码： bubble.py.zip (753 Bytes, 下载次数: 6, 售价: 5 鱼币)

2022-3-9 18:49 上传

点击文件名下载附件

用代码实现了冒泡算法后，来个实际应用：

将图书排行榜销量进行排序。

众所周知，小甲鱼老师已出版了 4 本教材，现有周销量如下：

{'零基础入门学习C语言':666,'零础入门学习Python':898,'零基础入门学习Scratch':381,'零基础入门学习Web开发':992}

我们用冒泡排序法将上面每本书按销量从低到高排列。



在开始排序前，给大家介绍一个神奇的 enumerate() 函数。

这个方法可以将一个可遍历的数据对象(如列表、元组或字符串)组合为一个索引序列，同时列出数据和数据下标，一般用在 for 循环当中。

例如：

>>> dst = ['one', 'two', 'three']
>>> for index, element in enumerate(dst):
...     print (index, element)
...
0 one
1 two
2 three

这样就可以直接获得下标与元素值。

index 用来排名，element 就是利用冒泡算法排序好的值。

由于我们我给的周销量是字典类型没法直接使用，需要先用  items() 方法以列表返回可遍历的(键, 值) 元组数组：



再使用 list() 转化：

data2 = list(data.items())

打印出 data2 中值：

for j in data2:
      print(j)

这时就跟之前一样要利用 bubble() 进行排序。

bubble(data2, key)

但此时 data2 中不仅我们要的具体值，还有书名，我们需要额外加个操作来提取下：

def key(x):
     return x[1]

返回传入项位置 1 的值，即销量。

由于我们定义了 def 函数， bubble 函数中的 key 形参可以不写，但写了肯定也没错。

结合 key() 操作，稍微修改下 bubble()：

def bubble(data,key):
    for i in range(len(data)-1,-1,-1):
        for j in range(i):
             if key(data[j])>key(data[i]):
                   data[i],data[j]=data[j],data[i]

最后就可以打印啦：

for index,i in enumerate(data2):
      print("第", 4-index,'名：',i)

搞定！

核心代码都实现了，完整代码自己去写～

源代码：

游客，如果您要查看本帖隐藏内容请回复

ckblt

看看

hornwong

zmy123

1

elven08

看看是什么，学习一下

忘无忧

求教

犬来猫荒