资源简介

(共25张PPT)
5.3.1 冒泡排序
数据排序
排序
排序就是整理数据的序列，使其中元素按照某个值的递增（或递减）
的次序重新排列的操作。在排序的过程中，数据元素的值保持不变，
但其在序列中的顺序可能会改变。
对于一次具体排序而言，总是针对某一组数据元素的某种具体的序关系
进行操作。待排序数据的存储方式一般有两种：一种是将数据依次存放
在一组地址连续的存储单元中，即以数组作为存储结构。在这种情况下，
排序过程是对数据本身进行物理重排，即通过关键字之间的比较判断，将
数据移到合适的位置。另一种存储方式是以链表作为存储结构，排序过程
中无须移动数据，仅需修改指针即可。
以数组为例，每个数组元素都对应存储一个数据。如下图所示，存储在
数组元素d[0]中的数据是23，d[1]中存储的是20，等等。
23 20 13 18 14 11
d
0
1
2
3
4
5
如果对数组d中的6个数据按升序进行排序，即调整数组d中所有数据的存储位置，使最小的数据存储在d[0]中，次小的数据存储在d[1]中……最大的数据存储在d[5]中。数组d中的所有数据满足：d[0]≤d[1]≤d[2]≤d[3]
≤d[4]≤d[5]。
这里两个数组元素的比较：d[i]≤d[j](i=0,1,…,5;j=0,1,…5)，指的是d[i]中
的数据小于或等于d[j]中的数据。
对数组d按升序进行排序后，数据的存储情况如下图所示。
11 13 14 18 20 23
d
0
1
2
3
4
5
Python中，对列表进行排序的方法有两种：一种是列表自带的sort方法，
只适用于列表，直接对列表进行排序，不会产生新的序列；另外一种是
内建函数sorted方法，返回一个新的序列，而原来的序列依然存在。两者
的使用方法如下所示：
a=[5,7,6,3,4,1,2]
b=sorted(a)
print(a)
[5,7,6,3,4,1,2]
print(b)
[1,2,3,4,5,6,7]
a.sort( )
print(a)
[1,2,3,4,5,6,7]
a.sort(reverse=True) #reverse=True实现按降序排序
print(a)
[7,6,5,4,3,2,1]
冒泡排序
冒泡排序是在一系列数据中对相邻
两个数依次进行比较和调整，让较
大的数“下沉（上冒）”，较小的
数“上冒（下沉）”的一种排序技
术。
23
20
13
18
14
11
d[5]
d[4]
d[3]
d[2]
d[1]
d[0]
20
23
13
18
14
11
20
13
23
18
14
11
20
13
18
23
14
11
20
13
18
14
23
11
20
13
18
14
11
23
①
②
③
④
⑤
冒泡排序算法对数组d的第一遍加工过程
冒泡排序算法对数组d的第二遍加工过程
20
13
18
14
11
23
13
20
18
14
11
23
13
18
20
14
11
23
13
18
14
20
11
23
13
18
14
11
20
23
①
②
③
④
冒泡排序算法对数组d的第三遍加工过程
13
18
14
11
20
23
13
18
14
11
20
23
13
14
18
11
20
23
13
14
11
18
20
23
①
②
③
冒泡排序算法对数组d的第四遍加工过程
13
14
11
18
20
23
13
14
11
18
20
23
13
11
14
18
20
23
①
②
冒泡排序算法对数组d的第五遍加工过程
13
11
14
18
20
23
11
13
14
18
20
23
①
对数组d来说，要排序的数共有6个，共需要5遍加工。
若要排序的数据有n个，则需要n-1遍加工。第i遍加工中，从第一个数开始，
相邻两数比较，若反序则交换两者的位置，直到第n+1-i个数为止。第一个数
与第二个数比较，第二个数与第三个数比较……第n-i个与第n+1-i个比较，
共比较n-i次。此时第n+1-i个位置上的数已经按要求排好，所以不参加以后
的比较和交换操作。
对n个元素的数组，用冒泡排序算法进行排序时，共需比较：
（n-1）+(n-2)+…+1=（次）
其时间复杂度为
O(n2)
排序过程中，按下面的方式使用变量i和j:
i:记录正进行的处理遍数，第1遍处理时值为1，第2遍处理时值为2，以此类推。
j:记录当前数组元素的下标。每遍处理过程中，j值总是从第一个数组元素的下标值0开始，按每次加1的方式，直至j=n-i-1为止。每当j取定一个值后，当前数组元素d[j]将与它的后一个元素d[j+1]进行比较，若d[j]>d[j+1]，则互换这两个数组元素中的数据。如下图所示是6个元素进行5遍加工的过程。
23
20
13
18
14
11
d[5]
d[4]
d[3]
d[2]
d[1]
d[0]
20
13
18
14
11
23
j
j+1
i=1
13
18
14
11
20
23
i=3
13
14
11
18
20
23
i=2
13
11
14
18
20
23
i=4
11
13
14
18
20
23
i=5
对规模为n的数组d，
冒泡排序的算法流程
图如图所示：
开始
是
i 1,L n
j＜L-i
j 0
i≤L-1
是
d[j]>d[j+1]
i i+1
否
交换d[j]和d[j+1]
否
j j+1
是
输出结果
结束
否
程序代码实现：
def bubble_sort(d):
length=len(d)
#序列长度为length，需要执行length-1遍加工
for i in range(1,length):
for j in range(0,length-i):
if d[j]>d[j+1]:
temp=d[j]
d[j]=d[j+1]
d[j+1]=temp
冒泡排序迁移应用及原理
1.冒泡排序迁移应用一（升序）
for i in range(1,n):
for j in range(n-1,i-1,-1):
if a[j]temp=a[j]
a[j]=a[j-1]
a[j-1]=temp
迁移原理：每一遍冒泡都是从后往前两两比较的，因此每遍排序达到的
效果是把最小值推到了最前面。
2.冒泡排序迁移应用二（升序）
n=len(a)
for i in range(n-1):
for j in range(n-2,i-1,-1):
if a[j+1]temp=a[j+1]
a[j+1]=a[j]
a[j]=temp
迁移原理：每一遍冒泡也是从后往前两两比较的，只是修改了内层循环中
部分代码。
3.冒泡排序迁移应用三（升序）
n=len(a)
for i in range(n-1):
for j in range(i+1,n):
if a[j]>a[i]:
a[i],a[j]=a[j],a[i]
迁移原理：在第i遍的排序中，把索引为i+1到索引为n-1的数组元素依次与
a[i]比较，如果比a[i]小，则两两交换。它的特点是所有的数与一个固定位置上的数进行比较。排序过程中，自前向后将数据进行有序排列。
4.冒泡排序的优化迁移
当某一遍排序过程中没有数据发生交换时，说明数据已经有序，无需进行下一遍排序，代码如下：
n=len(a)
flag=True #flag值为True表示一遍加工中发生过交换
i=1
while i<=n-1 and flag==True:
flag=False
for j in range(n-1,i-1,-1):
if a[j]a[j],a[j-1]=a[j-1],a[j]
flag=True
i+=1
迁移原理：用一个逻辑变量flag标记某一遍排序过程中是否有数据交换
另一种写法：
n=len(a)
flag=True #flag值为True表示一遍加工中发生过交换
i=1
while i<=n-1 and flag==True:
flag=False
for j in range(n-1,i-1,-1):
if a[j]a[j],a[j-1]=a[j-1],a[j]
flag=True
if flag==False:
break
i+=1
迁移原理：这种写法的排序遍数是i，在循环体内遇到了break语句，程序
跳出该循环，不再执行“i+=1”指令。
练一练
1.采用冒泡排序算法对数据序列“1,7,2,5,12,15,27,10,6,30”完成
升序排序，理论上讲共需进行排序的遍数为（ ）
A.6遍 B.7遍 C.8遍 D.9遍
2.采用冒泡排序算法对数据序列“2,15,7,5,9,18,30,25”完成降序排序，共需进行数据交换的次数为（ ）
A.21次 B.22次 C.23次 D.24次
D
C
3.采用冒泡排序算法对8个数据“18,15,9,3,7,5,16,21”进行降序排序，
则第2遍的排序结果是（ ）
原始数据 18,15,9,3,7,5,16,21
第1遍完成后的数据为 21,18,15,9,3,7,5,16
第2遍完成后的数据为
第3遍完成后的数据为
A.21,18,16,15,9,7,5,3
B.21,18,16,15,9,3,7,5
C.21,18,16,15,9,7,3,5
D.21,18,16,15,9,3,5,7
B
4.若冒泡排序在某一遍加工过程中没有数据交换，则说明数据已经有序，
优化程序段如下：
a=[58,36,23,97,77]
n=len(a)
i=1
flag=True
while i<=4 and flag==True:
flag=Flase
for j in range(4,i-1,-1):
if a[j]>a[j-1]:
a[j],a[j-1]=a[j-1],a[j]
flag=True
i+=1
数组元素a[0]到a[4]的值依次为“58,36,23,97,77”，经过该程序段“加
工”后，变量i的值是___________。
4
谢 谢

展开更多......

收起↑