本文共 3915 字,大约阅读时间需要 13 分钟。
数据结构——冒泡排序
1. 概念
排序: 将一组无序的记录序列调整为有序的记录序列 列表排序: 将无序列表变为有序列表 Python内置排序函数: sort()
常见排序算法 - 排序LOW B 三人组: 冒泡排序、选择排序、插入排序
- 排序NB三人组: 快速排序、堆排序、归并排序
- 其他排序: 希尔排序、计数排序、基数排序…
2. 冒泡排序
<1> 概念:
列表每两个相邻的数,如果前面比后面大,则交换这两个数一趟排序完成后,则无序区减少一个数,有序区增加一个数。
<2>排序过程:
比如现在有一个无序列表[3, 2, 5, 6, 4, 9, 7, 1]需要用冒泡排序法进行排序,如下图:
- 第零趟(i = 0): 0.1 第一步: j = 0, 即j指向3的位置,所以从3开始,把3和后面的2比较,发现3>2,则交换位置,结果为: 0.2 第二步: j = 1,即j指向3的位置,把3和后面的5比较,发现3<5,则不交换位置,结果为: 0.3 第三步: j = 2,即j指向5的位置,把5和后面的6比较,发现5<6,则不交换位置,结果为: 0.4 第四步: j = 3,即j指向6的位置,把6和后面的4比较,发现6>4,则交换位置,结果为: 0.5 第五步: j = 4,即j指向6的位置,把6和后面的9比较,发现6<9,则不交换位置,结果为: 0.6 第六步: j = 5,即j指向9的位置,把9和后面的7比较,发现9>7,则交换位置,结果为: 0.7 第七步: j = 5,即j指向9的位置,把9和后面的7比较,发现9<1,则交换位置,结果为: 第零趟结束后,最大值9就被放到了最后,目前的有序区只有一个9,而前面部分都是无序区(褐色为无序区,绿色为有序区):
- 第一趟(i = 1),在无序区进行排序: 1.1 第一步: j = 0, 即j指向2的位置,把2和后面的3比较,发现2<3,则不交换位置,结果为: 1.2 第二步: j = 1, 即j指向3的位置,把3和后面的5比较,发现3<5,则不交换位置,结果为: 1.3 第三步: j = 2, 即j指向5的位置,把5和后面的4比较,发现5>4,则交换位置,结果为: 1.4 第四步: j = 3, 即j指向5的位置,把5和后面的6比较,发现5<6,则不交换位置,结果为: 1.5 第五步: j = 4, 即j指向6的位置,把6和后面的7比较,发现6<7,则不交换位置,结果为: 1.6 第六步: j = 5, 即j指向7的位置,把7和后面的1比较,发现7>1,则交换位置,结果为: 第一趟结束后,7,9按升序被放到了最后两个,目前的有序区有7,9,而前面部分都是无序区(褐色为无序区,绿色为有序区):
- 第二趟(i = 2),在无序区进行排序: 2.1 第一步: j = 0, 即j指向2的位置,把2和后面的3比较,发现2<3,则不交换位置,结果为: 2.2 第二步: j = 1, 即j指向3的位置,把3和后面的4比较,发现3<4,则不交换位置,结果为: 2.3 第三步: j = 2, 即j指向4的位置,把4和后面的5比较,发现4<5,则不交换位置,结果为: 2.4 第四步: j = 3, 即j指向5的位置,把5和后面的6比较,发现5<6,则不交换位置,结果为: 2.5 第五步: j = 4, 即j指向6的位置,把6和后面的1比较,发现6>1,则交换位置,结果为: 第二趟结束后,6,7,9按升序被放到了最后三个,目前的有序区有6,7,9,而前面部分都是无序区(褐色为无序区,绿色为有序区):
- 第三趟(i = 3),在无序区进行排序: 3.1 第一步: j = 0, 即j指向2的位置,把2和后面的3比较,发现2<3,则不交换位置,结果为: 3.2 第二步: j = 1, 即j指向3的位置,把3和后面的4比较,发现3<4,则不交换位置,结果为: 3.3 第三步: j = 2, 即j指向4的位置,把4和后面的5比较,发现4<5,则不交换位置,结果为: 3.4 第四步: j = 3, 即j指向5的位置,把5和后面的1比较,发现5>1,则交换位置,结果为: 第三趟结束后,5,6,7,9按升序被放到了最后四个,目前的有序区有5,6,7,9,而前面部分都是无序区(褐色为无序区,绿色为有序区):
- 第四趟(i = 4),在无序区进行排序: 4.1 第一步: j = 0, 即j指向2的位置,把2和后面的3比较,发现2<3,则不交换位置,结果为: 4.2 第二步: j = 1, 即j指向3的位置,把3和后面的4比较,发现3<4,则不交换位置,结果为: 4.3 第三步: j = 2, 即j指向4的位置,把4和后面的1比较,发现4>1,则交换位置,结果为: 第四趟结束后,4,5,6,7,9按升序被放到了最后五个,目前的有序区有4,5,6,7,9,而前面部分都是无序区(褐色为无序区,绿色为有序区):
- 第五趟(i = 5),在无序区进行排序: 5.1 第一步: j = 0, 即j指向2的位置,把2和后面的3比较,发现2<3,则不交换位置,结果为: 5.2 第二步: j = 1, 即j指向3的位置,把3和后面的1比较,发现3>1,则交换位置,结果为: 第五趟结束后,3,4,5,6,7,9按升序被放到了最后六个,目前的有序区有3,4,5,6,7,9,而前面部分都是无序区(褐色为无序区,绿色为有序区):
- 第六趟(i = 6),在无序区进行排序: 6.1 第一步: j = 0, 即j指向2的位置,把2和后面的1比较,发现2>1,则交换位置,结果为: 第六趟结束后,所有的数字都排序完毕,无序区里没有数字,数字都在有序区:
<3>代码-code
def bubble_sort(li): for i in range(len(li-1)): #第 i 趟 for j in range(len(li) - i - 1): # 第 j 步 if li[j] > li[j+1]: li[j], li[j+1] = li[j+1], li[j] print(li)
运行一下:
li = [3, 2, 5, 6, 4, 9, 7, 1]bubble_sort(li)
打印一下排序过程:
[2, 3, 5, 4, 6, 7, 1, 9][2, 3, 4, 5, 6, 1, 7, 9][2, 3, 4, 5, 1, 6, 7, 9][2, 3, 4, 1, 5, 6, 7, 9][2, 3, 1, 4, 5, 6, 7, 9][2, 1, 3, 4, 5, 6, 7, 9][1, 2, 3, 4, 5, 6, 7, 9]
最后结果为:
[1, 2, 3, 4, 5, 6, 7, 9]
3. 冒泡排序改进
<1>栗子
先看个例子:
用我们上面的冒泡排序算法:
当我们要排序的列表为
[9, 7, 6, 5, 1, 2, 3, 4]
则排序过程为:
[7, 6, 5, 1, 2, 3, 4, 9][6, 5, 1, 2, 3, 4, 7, 9][5, 1, 2, 3, 4, 6, 7, 9][1, 2, 3, 4, 5, 6, 7, 9][1, 2, 3, 4, 5, 6, 7, 9][1, 2, 3, 4, 5, 6, 7, 9][1, 2, 3, 4, 5, 6, 7, 9]
这里我们可以发现,在第3趟的时候,列表已经排好序了,即[1, 2, 3, 4, 5, 6, 7, 9]
,此时按照原来的算法,第三趟结束时应该是把5
给冒上来,即把5
放到有序区,但是,这里第三趟结束后5
之前的无序区也排好序了,因为,我们输入时,就是1, 2, 3, 4
排好序的,不过按照原来的算法,就算排好序,我们还是要接着排,直到for循环结束,这样就降低了效率。
所以我们将算法进行改进,设置一个交换标志项,刚开始设为False,如果一趟下来,只要有一步进行了交换,则设为True,说明列表还是无序的,但如果一趟下来,都没有进行过交换,则说明此时,列表已经有序,我们可以直接输出!
<2>代码-code
def bubble_sort_improve(li): for i in range(len(li)-1): # 第 i 趟 exchange = False for j in range(len(li) - i - 1): if li[j] > li[j+1]: li[j], li[j + 1] = li[j + 1], li[j] exchange = True print(li) if not exchange: return
运行一下:
li = [9, 7, 6, 5, 1, 2, 3, 4]bubble_sort_improve(li)
过程为:
[7, 6, 5, 1, 2, 3, 4, 9][6, 5, 1, 2, 3, 4, 7, 9][5, 1, 2, 3, 4, 6, 7, 9][1, 2, 3, 4, 5, 6, 7, 9][1, 2, 3, 4, 5, 6, 7, 9]
可以发现,排序过程少了几步!
4. 时间复杂度
冒泡排序有两个循环嵌套,所以时间复杂度为: O ( n 2 ) O(n^2) O(n2)
转载地址:http://nfiwi.baihongyu.com/