文档介绍：第6章排序与选择
学习要点:
理解排序问题的实质。
掌握简单排序算法的设计思想与分析方法。
掌握快速排序算法的设计思想与分析方法。
理解随机化思想在快速排序算法中的应用。
掌握合并排序算法的基本思想及实现方法。
掌握计数排序算法的设计思想与分析方法。
掌握桶排序算法的设计思想与分析方法。
理解线性时间排序与基于比较排序算法的主要差别和适用范围。
掌握平均情况下线性时间选择算法的设计思想与分析方法。
掌握最坏情况下线性时间选择算法的设计思想与分析方法。
11/11/2017
1
福州大学数学与计算机科学学院
基本概念与术语
(1)数据对象(记录)的键值key和卫星数据
(2)稳定的排序算法与不稳定的排序算法
(3)就地排序与非就地排序
(4)排序中的基本操作:比较和移动(交换)
(5)排序算法复杂度的度量:
算法步数
键值比较次数
11/11/2017
2
福州大学数学与计算机科学学院
排序算法分类
基于比较的排序算法
交换排序
冒泡排序
快速排序
插入排序
直接插入排序
二分插入排序
Shell排序
选择排序
简单选择排序
堆排序
合并排序
基于数字和地址计算的排序方法
计数排序
桶排序
基数排序
11/11/2017
3
福州大学数学与计算机科学学院
冒泡排序
基本思想:
将第一个记录的关键字与第二个记录的关键字进行比较,若为逆序(即:a[0].key>a[1].key),则交换;然后比较第二个记录与第三个记录;依次类推,直至第n-1个记录和第n个记录比较为止——第一趟冒泡排序,结果关键字最大的记录被安置在最后一个记录上
对前n-1个记录进行第二趟冒泡排序,结果使关键字次大的记录被安置在第n-1个记录位置
重复上述过程,直到“在一趟排序过程中没有进行过交换记录的操作”为止
简单排序算法
11/11/2017
4
福州大学数学与计算机科学学院
算法描述
算法分析
时间复杂度
最好情况(正序)
比较次数:n-1
交换次数:0
最坏情况(逆序)
比较次数:
交换次数:
∴ T(n)=O(n²)
11/11/2017
5
福州大学数学与计算机科学学院
直接插入排序
基本思想:
整个排序过程为n-1趟插入,即先将序列中第1个记录看成是一个有序子序列,然后从第2个记录开始,逐个进行插入,直至整个序列有序。
简单排序算法
11/11/2017
6
福州大学数学与计算机科学学院
例
49 38 65 97 76 13 27
i=1 38 (38 49) 65 97 76 13 27
i=2 65 (38 49 65) 97 76 13 27
i=3 97 (38 49 65 97 ) 76 13 27
i=4 76 (38 49 65 76 97) 13 27
i=5 13 (13 38 49 65 76 97) 27
i=0 ( )
i=6 (13 38 49 65 76 97 ) 27
27
j=i-1
j
j
j
j
j
97
76
65
49
38
27
(13 27 38 49 65 76 97)
排序结果:
11/11/2017
7
福州大学数学与计算机科学学院
算法分析
时间复杂度
若待排序记录按关键字从小到大排列(正序)
关键字比较次数:
记录交换次数:
若待排序记录按关键字从大到小排列(逆序)
关键字比较次数:
记录交换次数:
∴ T(n)=O(n²)
算法描述
11/11/2017
8
福州大学数学与计算机科学学院
二分插入排序
基本思想:用二分查找方法确定插入位置的排序叫~
例
i=1 (30) 13 70 85 39 42 6 20
i=2 13 (13 30) 70 85 39 42 6 20
i=7 6 (6 13 30 39 42 70 85 ) 20
…...
i=8 20 (6 13 30 39 42 70 85 ) 20
s
j
m
i=8 20 (6 13 30 39 42 70 85 ) 20
s
j
m
i=8 20 (6 13 30 39 42 70 85 ) 20
s
j
m
i=8 20 (6 13 30 39 42 70 85 ) 20
s
j
i=8 20 (6 13 20 30 39 42 70 85 )
11/11/2017
9
福州大学数学与计算机科学学院
算法描述
算法评价
时间复杂度:T(n)=O(n²)
空间复杂度:S(n)=O(n)
11/11/2017
10
福州大学数学与计算机科学学院