5.3.1 数据排序 课件（28张PPT）

(共28张PPT)
5.3.1 数据排序（第一课时）
单击此处添加副标题
思考1：什么是排序？
一、排序的概念
排序就是整理数据的序列，使其中元素按照某个值的递增（或递减）的次序重新排列的操作。
在排序的过程中，数据元素的值保持不变，但其在序列中的顺序可能发生变化。
思考2：怎么排序？
二、数据的组织形式 （以Python语言环境为例）
待排序数据的存储方式一般有两种：
（1）以数组作为存储结构
将数据依次存放在一组地址连续的存储单元中，通过关键字之间的比较判断，将数据移到合适的位置进行物理重排
（2）以链表作为存储结构
对链表进行排序无须移动数据，比较判断后，只修改指针即可。
待排序数据的存储方式一般有两种：
（1）以数组作为存储结构
将数据依次存放在一组地址连续的存储单元中，通过关键字之间的比较判断，将数据移到合适的位置进行物理重排
（2）以链表作为存储结构
对链表进行排序无须移动数据，比较判断后，只修改指针即可。
二、数据的组织形式 （以Python语言环境为例）
思考3：数组的排序如何实现？
三、Python中的排序函数
1.内建函数sorted()：返回一个新序列，而原序列依然存在
2.列表自带的sort方法：直接对列表排序，不产生新序列
以a=[23,20,13,18,14,11]为例
三、Python中的排序函数
>>>a.sort( )
>>>print(a)
>>>a.sort(reverse=True) #reverse=True实现降序排序
>>>print(a)
>>>b=sorted(a)
>>>print(b)
>>>print(a)
以a=[23,20,13,18,14,11]为例
[11,13,14,18,20,23]
[23,20,13,18,14,11]
[11,13,14,18,20,23]
[23,20,18,14,13,11]
知其然
知其所以然
1.内建函数sorted()：返回一个新序列，而原序列依然存在
2.列表自带的sort方法：直接对列表排序，不产生新序列
四、常见的排序算法
思考4: 若请你设计一个实现排序
的算法，你会如何设计？
冒泡排序
出处：十大经典排序算法 https:///onepixel/articles/7674659.html
四、常见的排序算法
选择排序
出处：十大经典排序算法 https:///onepixel/articles/7674659.html
四、常见的排序算法
插入排序
出处：十大经典排序算法 https:///onepixel/articles/7674659.html
四、常见的排序算法
冒泡排序、选择排序、插入排序、快速排序、
堆排序、归并排序、桶排序……
出处：十大经典排序算法 https:///onepixel/articles/7674659.html
五、冒泡排序算法及其程序实现
算法思想：在一系列数据中对相邻两个数依次进行比较和
调整，让较大的数“下沉（或上冒）”，较小
的数“上冒（或下沉）”的一种排序方法。
前 后
前 后
前 后
前 后
五、冒泡排序算法及其程序实现
23
20
13
18
14
11
a[5]
a[4]
a[3]
a[2]
a[1]
a[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
①
②
③
④
⑤
第一遍加工过程
若将n个元素的数组看成是垂直堆放的一列数据
（以从上往下比，将大数往下沉，实现升序排序为例）
五、冒泡排序算法及其程序实现
20
13
18
14
11
23
a[5]
a[4]
a[3]
a[2]
a[1]
a[0]
13
20
18
14
11
23
13
18
20
14
11
23
13
18
14
20
11
23
13
18
14
11
20
23
①
②
③
④
第二遍加工过程
若将n个元素的数组看成是垂直堆放的一列数据
（以从上往下比，将大数往下沉，实现升序排序为例）
……
五、冒泡排序算法及其程序实现
13
11
14
18
20
23
a[5]
a[4]
a[3]
a[2]
a[1]
a[0]
11
13
14
18
20
23
①
第五遍加工过程
若将n个元素的数组看成是垂直堆放的一列数据
（以从上往下比，将大数往下沉，实现升序排序为例）
若要排序的数有6个，
则需经过 遍加工
11
13
14
18
20
23
5
五、冒泡排序算法及其程序实现
思考5：
1.若要排序的数有n个，则需经过 遍加工
2.对n个元素的数组，用冒泡排序算法排序时，共需比较：
3.其时间复杂度为:
n-1
(n-1)+(n-2)+…+1=（次）
O(n2)
五、冒泡排序算法及其程序实现
排序过程中，按下面的方式使用变量i和j:
i:记录正进行的处理遍数（ ）
j:记录当前比较元素的下标( )
a[5]
a[4]
a[3]
a[2]
a[1]
a[0]
j
j+1
i=1
i=3
i=2
i=4
i=5
1 n-1
0 n-i-1
j
0
n-2
j
0
n-3
五、冒泡排序算法及其程序实现
开始
是
j＜n-i
i≤n-1
是
d[j]>d[j+1]
i i+1
否
交换d[j]和d[j+1]
否
是
输出结果
结束
否
i 1
j 0
j j+1
流程图：
五、冒泡排序算法及其程序实现
程序代码实现：
def bubble_sort(a):
n=len(a)
#序列长度为n，需要执行n-1遍加工
for i in range(1, n):
for j in range( 0 , n-i ):
if a[j] > a[j+1]:
a[j],a[j+1]=a[j+1], a[j]
思考6：若要实现降序排序，如何修改代码？
<
思考7：若从后往前加工，如何修改代码？
无序区
有序区
无序区
有序区
课堂小结：
1.排序的概念
2.Python中的排序函数
3.常见的排序算法
4.冒泡排序的算法过程及代码实现
评分项 自我评价
理解排序的基本概念 5 4 3 2 1
掌握Python中的排序函数 5 4 3 2 1
能够了解常见的排序算法 5 4 3 2 1
初步掌握冒泡排序的算法过程及代码实现 5 4 3 2 1
学习评价：
对自己的表现进行客观的评价，并思考后续完善的
方向。（5=优秀，4=超出一般水平，3=满意，2=有待
改进，1=不太理想）
同学们，再见！
单击此处添加副标题