首页 > 编程笔记

Python冒泡排序算法(附带源码和解析)

排序算法几乎可以说是最常使用到的一种算法。所谓排序,就是将一组数据按照某一个特定规则重新排列,使其具有递增或递减的次序关系。用以排序的依据称为键,它所含的值就称为键值。

排序算法——冒泡排序法

冒泡排序法是很常见的排序法,又称为交换排序法,是人们通过观察水中的气泡变化构思而成的。气泡随着不同水深处的压力而改变。气泡在水底时,水压最大,气泡最小;当慢慢浮上水面时,气泡由小渐渐变大。

冒泡排序法的比较方式是由第 1 个元素开始,比较两个相邻元素的大小,若大小顺序有误,则交换两个元素,然后再进行下一个元素的比较。如此比较过一遍之后就可确保最后一个元素位于正确的位置,接着再逐步进行第 2 遍比较,直到完成所有元素的排序为止。

以下排序示范了 6、4、9、8、3 数列的排序过程,读者可以清楚地知道冒泡排序法的执行流程,原始顺序如图 1 所示。

图1
图1
上述数列排序过程:


图2
图2


图3
图3

图4
图4

图5
图5

由此可知,5 个元素的冒泡排序法必须执行(5-1)遍比较,第一遍比较需比较(5-1)次,共比较 4+3+2+1=10次。

Python冒泡排序法应用

我们设计一个 Python 程序,并使用冒泡排序法来将以下的数列排序。

99,95,90,88,78,67,33,26,12


【示例1】冒泡排序法的应用。Python 代码如下:
data=[99,95,90,88,78,67,33,26,12]#原始顺序
print('冒泡排序法:原始顺序为:')
for i in range(len(data)):
    print('%3d' %data[i],end='')
print()

for i in range(len(data)-1,0,-1): #比较遍数
    for j in range(i):
        if data[j]>data[j+1]:#比较、交换的次数
            data[j],data[j+1]=data[j+1],data[j]#比较相邻两数,如果前面的数较大则交换
    print('第 %d 遍比较后的结果是:' %(len(data)-i),end='') #把各遍比较后的结果输出

    for j in range(len(data)):
        print('%3d' %data[j],end='')
    print()

print('排序后的结果为:')
for j in range(len(data)):
    print('%3d' %data[j],end='')
print()
输出结果:

冒泡排序法:原始顺序为:
99 95 90 88 78 67 33 26 12
第 1 遍比较后的结果是: 95 90 88 78 67 33 26 12 99
第 2 遍比较后的结果是: 90 88 78 67 33 26 12 95 99
第 3 遍比较后的结果是: 88 78 67 33 26 12 90 95 99
第 4 遍比较后的结果是: 78 67 33 26 12 88 90 95 99
第 5 遍比较后的结果是: 67 33 26 12 78 88 90 95 99
第 6 遍比较后的结果是: 33 26 12 67 78 88 90 95 99
第 7 遍比较后的结果是: 26 12 33 67 78 88 90 95 99
第 8 遍比较后的结果是: 12 26 33 67 78 88 90 95 99
排序后的结果为:
12 26 33 67 78 88 90 95 99

程序解说:
传统的冒泡排序法存在缺陷:不管数据是否已排序完成,都固定会执行 n(n-1)÷2次。

数列在什么情况下才是已经排好序呢?——在一轮比较当中,如果没有出现数据交换的情况,则表示当前数列中每相邻的两个数据都是后面的比前面大(或者小),也就是数列已经处于有序状态。

下面设计一个 Python 程序,引入一个变量,通过该变量的值来判断数据是否已排好序,这样可以提前中断程序来提高程序的执行效率。

【示例2】改良的冒泡排序法。python代码如下:
#加入变量的改良冒泡排序法
def showdata(data):    #利用循环输出数据
    for i in range(len(data)):
        print('%3d' %data[i],end='')
    print()
   
def bubble (data):
    for i in range(len(data)-1,0,-1):
        flag=0 #flag用来判断是否有执行交换的动作
        for j in range(i):
            if data[j+1]<data[j]:
                data[j],data[j+1]=data[j+1],data[j]
                flag+=1  #如果执行过交换,则flag不为0
        if flag==0:
            break
        #当执行完一遍比较就判断是否做过交换动作,如果没有交换过数据,表示此时数组已完成排序,故可直接跳出循环  
        print('第 %d 轮排序:' %(len(data)-i),end='')
        for j in range(len(data)):
            print('%3d' %data[j],end='')
        print()
    print('排序后结果为:',end='')
    showdata (data)

def main():
    data=[1,2,3,4,5,6,8,9,7]  #原始顺序
    print('原始顺序:')
    showdata(data)
    print('改良冒泡排序法的原始顺序为:')
    bubble (data)
   
main()
输出结果:

原始顺序:
  1  2  3  4  5  6  8  9  7
改良冒泡排序法的原始顺序为:
第 1 轮排序:  1  2  3  4  5  6  8  7  9
第 2 轮排序:  1  2  3  4  5  6  7  8  9
排序后结果为:  1  2  3  4  5  6  7  8  9

程序解说:

优秀文章