21.冒泡排序算法

四曲

2020 年 12 月 29 日

607 次浏览

暂无评论

4289字数

Python笔记

什么是冒泡排序算法

在前面，我们讲过了什么是排序算法以及选择排序算法如何去实现，实际上，排序算法的种类很多，不仅仅只有选择排序算法，还有其他的排序算法，那我们今天就学习一种新的排序算法，叫做冒泡排序算法

那我们先通过一个简单的视频来了解一下什么是冒泡排序算法

我们可以看到，冒泡排序算法其实不难理解，我们只需要对相邻的两个数据进行比较，如果前面一个数据比后面一个数据大，那么我们就把它们两个进行元素交换，如此不断进行，一轮交换完成之后，我们就发现最大的数已经放在列表的最后面的，就像一个泡泡一样，慢慢的冒出来，因此，我们就把它叫做冒泡排序算法

假设我们现在有这样的一个列表[45,101,89,90,34,78,23]，那么我们来看看整个排序过程

将从索引0和索引1的数据开始比较，如果前面一个数据大于后一个数据，那么将它们交换位置，一轮完成交换后的结果：[45, 89, 90, 34, 78, 23, 101]
从头开始比较，由于101已经排序好了，所以我们不需要对它进行排序，结果：[45, 89, 34, 78, 23, 90, 101]
不断重复进行，由于总共有7个数据，每次排序好一个数据，最后剩下的一个数据不需要进行排序，因此进行6轮排序即可，最后可以得到正确结果：[23, 34, 45, 78, 89, 90, 101]

如果还是不明白，那么我们借助JL编程来进行动画演示

实现算法

那么知道了冒泡排序的过程之后，我们可以先画出流程图

冒泡排序法

我们就可以用代码来实现它了，对于第一轮来说，总共有7个数据，但是我们只需要排列6次，如果前一个数据大于后一个数据，那么就将它们进行交换

for i in range(len(List)-1):    #只需要比较6次，因此需要减1
    if List[i]>List[i+1]:
        List[i],List[i+1]=List[i+1],List[i]
print(List)

对于第二轮循环来说，由于最后一个已经排序完成，因此，只需要进行5次比较

for i in range(len(List)-2):    #只需要比较5次，因此需要减2
    if List[i]>List[i+1]:
        List[i],List[i+1]=List[i+1],List[i]
print(List)

那么我们只需要进行6轮比较即可，到了六轮比较时，循环次数就变成了range(len(List)-6)，我们能够从中发现规律，因此，我们可以统一用一个大循环将它们组织起来

List=[45,101,89,90,34,78,23]

for j in range(len(List)-1):
    for i in range(len(List)-(j+1)):
        if List[i]>List[i+1]:
            List[i],List[i+1]=List[i+1],List[i]
    print(List)
    
# [45, 89, 90, 34, 78, 23, 101]
# [45, 89, 34, 78, 23, 90, 101]
# [45, 34, 78, 23, 89, 90, 101]
# [34, 45, 23, 78, 89, 90, 101]
# [34, 23, 45, 78, 89, 90, 101]
# [23, 34, 45, 78, 89, 90, 101]

到此为止，我们就完成了整个排序过程

优化算法

实际上，这个冒泡排序算法还有很多值得优化的地方，比如对下面这个列表进行排序

List=[45,23,89,90,34,78,23]

for j in range(len(List)-1):
    for i in range(len(List)-(j+1)):
        if List[i]>List[i+1]:
            List[i],List[i+1]=List[i+1],List[i]
    print(List)

# [23, 45, 89, 34, 78, 23, 90]
# [23, 45, 34, 78, 23, 89, 90]
# [23, 34, 45, 23, 78, 89, 90]
# [23, 34, 23, 45, 78, 89, 90]
# [23, 23, 34, 45, 78, 89, 90]
# [23, 23, 34, 45, 78, 89, 90]

我们可以发现，最后一轮排序是无用交换，因为我们没有进行任何交换，这点实际上是值得去优化的，我们来新建一个变量，用于记录是否发生交换，如果没有发生交换，那么我们就说，这个列表已经排序完成了

List=[23,34,45,89,90,78,23]

for j in range(len(List)-1):
    isswap=False
    for i in range(len(List)-(j+1)):
        if List[i]>List[i+1]:
            isswap=True
            List[i],List[i+1]=List[i+1],List[i]
    if isswap==False:
        break
    print(List)

# [23, 34, 45, 89, 78, 23, 90]
# [23, 34, 45, 78, 23, 89, 90]
# [23, 34, 45, 23, 78, 89, 90]
# [23, 34, 23, 45, 78, 89, 90]
# [23, 23, 34, 45, 78, 89, 90]

封装成通用方法

同样地，我们可以把冒泡排序也封装成一个通用方法，以便于我们使用

def bubble_sort(List):
    for j in range(len(List)-1):
        isswap=False
        for i in range(len(List)-(j+1)):
            if List[i]>List[i+1]:
                isswap=True
                List[i],List[i+1]=List[i+1],List[i]
        if isswap==False:
            break


List1=[23,34,45,89,90,78,23]
List2=[45,12,90,3,34,67,45]

bubble_sort(List1)
bubble_sort(List2)

print(List1)
print(List2)

# [23, 23, 34, 45, 78, 89, 90]
# [3, 12, 34, 45, 45, 67, 90]

算法时间比较

我们以前学习过选择排序算法，那么我们可以利用random库与time库来比较两个算法，看看哪个算法的效率较高

import random
import time

#冒泡排序算法
def bubble_sort(List):
    a=List
    for j in range(len(List)-1):
        isswap=False
        for i in range(len(List)-(j+1)):
            if List[i]>List[i+1]:
                isswap=True
                List[i],List[i+1]=List[i+1],List[i]
        if isswap==False:
            break
    return a

#选择排序算法
def sort_funtion(List):
    a=List
    for j in range(len(a)):
        minindex=j
        for i in range(j,len(a)):
            if a[i]<=a[minindex]:
                minindex=i
        temp=a[minindex]
        a[minindex]=a[j]
        a[j]=temp
    return a

List=[]
for i in range(5000):
    List.append(random.randint(1,10000))

start=time.time()
bubble_sort(List)
end=time.time()
print("冒泡排序算法用时：",end-start)


start=time.time()
sort_funtion(List)
end=time.time()
print("选择排序算法用时：",end-start)

# C:\Users\heyang\Desktop>test.py
# 冒泡排序算法用时： 3.482654571533203
# 选择排序算法用时： 1.14493989944458

# C:\Users\heyang\Desktop>test.py
# 冒泡排序算法用时： 3.4387686252593994
# 选择排序算法用时： 1.2476959228515625

我们可以看到两种算法之间的效率，显然，选择排序的速度会比冒泡排序算法的速度快