Python冒泡排序算法(附带源码和解析)
排序算法几乎可以说是最常使用到的一种算法。所谓排序,就是将一组数据按照某一个特定规则重新排列,使其具有递增或递减的次序关系。用以排序的依据称为键,它所含的值就称为键值。
冒泡排序法的比较方式是由第 1 个元素开始,比较两个相邻元素的大小,若大小顺序有误,则交换两个元素,然后再进行下一个元素的比较。如此比较过一遍之后就可确保最后一个元素位于正确的位置,接着再逐步进行第 2 遍比较,直到完成所有元素的排序为止。
以下排序示范了 6、4、9、8、3 数列的排序过程,读者可以清楚地知道冒泡排序法的执行流程,原始顺序如图 1 所示。
图1
上述数列排序过程:
图2
图3
图4
图5
由此可知,5 个元素的冒泡排序法必须执行(5-1)遍比较,第一遍比较需比较(5-1)次,共比较 4+3+2+1=10次。
【示例1】冒泡排序法的应用。Python 代码如下:
传统的冒泡排序法存在缺陷:不管数据是否已排序完成,都固定会执行
数列在什么情况下才是已经排好序呢?——在一轮比较当中,如果没有出现数据交换的情况,则表示当前数列中每相邻的两个数据都是后面的比前面大(或者小),也就是数列已经处于有序状态。
下面设计一个 Python 程序,引入一个变量,通过该变量的值来判断数据是否已排好序,这样可以提前中断程序来提高程序的执行效率。
【示例2】改良的冒泡排序法。python代码如下:
排序算法——冒泡排序法
冒泡排序法是很常见的排序法,又称为交换排序法,是人们通过观察水中的气泡变化构思而成的。气泡随着不同水深处的压力而改变。气泡在水底时,水压最大,气泡最小;当慢慢浮上水面时,气泡由小渐渐变大。冒泡排序法的比较方式是由第 1 个元素开始,比较两个相邻元素的大小,若大小顺序有误,则交换两个元素,然后再进行下一个元素的比较。如此比较过一遍之后就可确保最后一个元素位于正确的位置,接着再逐步进行第 2 遍比较,直到完成所有元素的排序为止。
以下排序示范了 6、4、9、8、3 数列的排序过程,读者可以清楚地知道冒泡排序法的执行流程,原始顺序如图 1 所示。
图1
- 第 1 遍比较会先拿第一个元素 6 和第 2 个元素 4 作比较,如果第 2 个元素小于第 1 个元素,则两个元素交换。接着拿 6 和 9 作比较,就这样一直比较并交换,到第 4 次比较完成后即可确定最大值在数组的最后面,如图 2 所示。
图2
- 第 2 遍比较亦从头开始,但因为最后一个元素在第1遍比较后就已确定是数组的最大值,所以只需要比较 3 次即可把剩余数组元素的最大值排到剩余数组的最后面,如图 3 所示。
图3
- 第 3 遍比较完成后,完成第 3 个值的排序,如图 4 所示。
图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
- 第1~5行:原始数据的输入及输出。
- 第7~14行:冒泡排序法的排序过程。
- 第17~19行:输出排序后的结果。
传统的冒泡排序法存在缺陷:不管数据是否已排序完成,都固定会执行
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
- 第 2~5 行:利用循环输出数据的函数。
- 第 7~23 行:改良冒泡排序法的函数定义。
- 第 25~30 行:定义一个类似主程序功能的函数,程序内容包括原始数据的输入与输出,并调用改良冒泡排序法的函数。
- 第 32 行:调用有主程序功能的 main() 函数。