资源简介

(共16张PPT)
第五章 数据结构与算法
选修一《数据与数据结构》
5.3.2 常见的排序算法——冒泡排序
排序就是整理数据的序列，使其中元素按照某个值递增（或递减）的次序重新排列的操作。
排序是什么？
太抽象了，无法理解
排序是什么？
18 9 14 12 7
18 9 14 12 7
按数组形式进行存储
18
9
14
12
7
按链表形式进行存储
7 9 12 14 18
对数组进行升序排序
Python中的排序实现
第一种：列表自带的sort算法
列表自带的sort方法，只适用于列表，直接对列表进行排序，不会产生新的序列。
第二种：内建函数sorted方法
内建函数sorted方法，返回一个新的序列，原来序列依然存在。
a=[5,7,6,3,4,1,2]
a.sort()
print(a) #[1,2,3,4,5,6,7]
a=[5,7,6,3,4,1,2]
a.sort( reverse=True )
print(a) #[7,6,5,4,3,2,1]
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]
常见的排序算法 — 冒泡排序
冒泡排序是在一系列数据中对相邻两个数依次进行比较和调整，让较大的数“下沉（上冒）”，较小的数“上冒（下沉）”的一种排序技术。
18
9
14
12
7
p[0]
p[1]
p[2]
p[3]
p[4]
9
18
14
12
7
9
14
18
12
7
9
14
12
18
7
9
14
12
7
18
冒泡排序算法对数组p做的第1遍加工
常见的排序算法 — 冒泡排序
9
14
12
7
18
9
14
12
7
18
9
12
14
7
18
9
12
7
14
18
冒泡排序算法对数组p做的第2遍加工
冒泡排序算法对数组p做的第3遍加工
9
12
7
14
18
9
12
7
14
18
9
7
12
14
18
常见的排序算法 — 冒泡排序
9
7
12
14
18
7
9
12
14
18
冒泡排序算法对数组p做的第4遍加工
对长度为5的数组p，一共需要4次加工
对长度为n的数组p
① 一共需要(n-1)次加工
② 在第i遍加工当中，共需比较(n-i)次
③ 总共需要比较次
① 一共需要(n-1)次加工
常见的排序算法 — 冒泡排序
9
14
12
7
18
9
12
7
14
18
9
7
12
14
18
7
9
12
14
18
排好第1大的元素
排好第2大的元素
排好第4大的元素
排好第3大的元素
每一次加工，都是为了排好未排序数据当中最大的元素
常见的排序算法 — 冒泡排序
② 在第i遍加工当中，共需比较(n-i)次
n=5
i=1
n-i=4
排好元素：i-1=0个
共有n-(i-1)=5个元素需要比较
两两比较需要比较4次
常见的排序算法 — 冒泡排序
② 在第i遍加工当中，共需比较(n-i)次
n=5
i=2
n-i=3
排好元素：i-1=1个
共有n-(i-1)=4个元素需要比较
两两比较需要比较3次
常见的排序算法 — 冒泡排序
② 在第i遍加工当中，共需比较(n-i)次
n=5
i=3
n-i=2
排好元素：i-1=2个
共有n-(i-1)=3个元素需要比较
两两比较需要比较2次
n=5
i=4
n-i=1
排好元素：i-1=3个
共有n-(i-1)=2个元素需要比较
两两比较需要比较1次
如果说一共有n个元素，第i遍加工当中
共有(n-i+1)个元素需要比较
两两比较需要比较(n-i)次
常见的排序算法 — 冒泡排序
③ 总共需要比较次
第1遍加工：比较（n-1）次
第2遍加工：比较（n-2）次
…
第（n-2）遍加工：比较2次
第（n-1）遍加工：比较1次
① 一共需要(n-1)次加工
Q：一共需要几次加工？
算法时间复杂度为
总共需要比较次数S
冒泡排序算法实现
自主阅读课本第130页，思考一共需要几个变量？每个变量的作用是什么？
i：记录当前正进行的处理遍数
j：记录当前数组元素的下标。
每遍处理过程中，
j总是从第一个数据元素，下标为0开始。
按每次加1的方式
直至j+1=n-i => j=n-i-1为止
每次比较p[j]与p[j+1]进行比较，
若p[j]>p[j+1]，则进行互换
i=2
j=0
j+1
j=1
j+1
j=2
j+1
j=3
j+1
i=1
i=1
i=1
i=1
j=0
j+1
j=1
j+1
j=2
j+1
i=2
i=2
i=3
i=3
i=4
j=0
j+1
j=1
j+1
j=0
j+1
每遍处理过程中，
j总是从第一个数据元素，下标为0开始。
按每次加1的方式
直至j+1=n-i => j=n-i-1为止
每次比较p[j]与p[j+1]进行比较，
若p[j]>p[j+1]，则进行互换
冒泡排序算法实现
i：记录当前正进行的处理遍数
j：记录当前数组元素的下标。
① 一共需要(n-1)次加工
冒泡排序算法实现
Python代码实现
def bubble_sort(p):
length = len(p)
for i in range(1, length):
for j in range(0, length-i):
if p[j]>p[j+1]:
temp = p[j]
p[j] = p[j+1]
p[j+1] = temp
return p
冒泡排序算法实现
课后作业：
课后了解选择排序、插入排序、快速排序、堆排序、归并排序、桶排序算法
并思考冒泡排序从大到小的Python实现方式

展开更多......

收起↑