广平专业做网站/汽车网络营销推广方案
数据结构——冒泡排序
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 = Falsefor j in range(len(li) - i - 1): if li[j] > li[j+1]:li[j], li[j + 1] = li[j + 1], li[j]exchange = Trueprint(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(n2)O(n^2)O(n2)