《数据结构 C++版 普通高等教育“十一五”国家级规划教材 教学课件 ppt 杨秀金 第9章 排序-1》由会员分享，可在线阅读，更多相关《数据结构 C++版 普通高等教育“十一五”国家级规划教材 教学课件 ppt 杨秀金 第9章 排序-1（41页珍藏版）》请在金锄头文库上搜索。
1、1,第9章 排序,第1讲,第6章 树与二叉树,2,第9章 排序,排序是一种重要运算，在很多领域中有广泛的应用。排序的方法很多，本章介绍典型高效排序方法，主要内容： 排序的基本概念和术语 插入排序：直接插入排序和希尔排序 交换排序：冒泡排序和快速排序 选择排序：简单选择排序和堆排序 归并排序 基数排序 各种排序方法的比较分析,3,本章分为（34）讲,第1讲 9.1 排序的基本概念 9.2 插入排序 9.3 交换排序,第3讲 9.5 归并排序 9.6 基数排序,第2讲 9.4 选择排序,供教师参考,9.1的希尔排序略讲或不讲. 9.3的快速排序的部分内容(算法实现)可放到第2讲.,9.6的基数排序
2、可略讲.,4,9.1 排序的基本概念,排序（Sorting）是数据处理领域中一种最常用的运算。排序又称分类。 排序：是把一组记录（元素）按照某个域的值的递增（即由小到大）或递减的次序重新排列的过程。可以使杂乱无章的数据序列重新排列成有序序列。 排序分两类：内部排序和外部排序。 本章主要讨论内部排序。,为了方便讨论，把排序所依据的数据项统称排序关键字，简称关键字。 假设含有n个记录的序列为：R1, R2， , Rn， 其相应的关键字序列为：K1，K2，Kn， 所谓排序就是将记录Ri 按关键字Ki 非递减（或非递增）的顺序重新排列起来。,5,排序的稳定性,在待排序的记录中若有多个相同的关键字，在采
3、用某种方法排序后，这些关键字相同的记录相对先后次序不变，则称这种排序方法是稳定的；否则是不稳定的。 本章所介绍的内部排序方法，大多数是通过比较关键字的大小决定记录的先后次序，也称为比较排序。基数排序是不经关键字比较的排序方法。,6,排序选用顺序存储,记录结构Data定义： const MAXSIZE=1000; /数组最大容量 typedef int ElemType; /关键字的类型 struct Data ElemType key; /排序关键字域 int oth ; /其他域，根据需要自定 ; 数组的定义如下： Data arMAXSIZE, brMAXSIZE;,7,9.2 插入排序,
4、插入排序（Insertion Sort）又可分几种不同的方法，主要介绍2种方法： 直接插入排序； 希尔排序；,8,9.2.1 直接插入排序,直接插入排序（Straight Insertion Sort）是一种最简单的排序方法。算法思路： 设有一组关键字K1，K2，Kn； 开始，认为K1是一个有序序列； 让K2插入表长为1的有序序列，使之成为一个表长为2的有序序列； 然后让K3插入表长为2的有序序列，使之成为一个表长为3的有序序列； 依此类推，最后让Kn插入表长为n1的有序序列，得一个表长为n的有序序列。,9,直接插入排序-例9.1,设有一组关键字序列55，22，44，11，33，这里n=5。按
5、由小到大的顺序排序。,10,算法9.1,template void stinsort ( T r , int n) int i,j; for (i=2; i r0.key) rj+1=rj; j-; rj+1=r0; /原ri插到rj后边 /sinsort,算法时间复杂度为(n2)。 当Kj 与K0 相等时并不移动记录，排序方法是稳定的。,11,上页是函数模板，类型抽象。具体排序时注意： const MAXSIZE=1000; /数组最大容量 typedef int ElemType; /关键字类型 struct DataElemType key; /关键字域 int oth； /其他域 ；
6、int main() Data sMAXSIZE; int n; cinn; /记录的个数, MAXSIZEn for(int i=1; isi.key; ; /为s数组提供数据 stinsort(s ,n); /调用函数模板 ,12,直接插入排序-算法分析,算法时间复杂度为(n2)。 当Kj 与K0 相等时并不移动记录，排序方法是稳定的。 在原关键字序列基本有序或n值较小时，是一种最常用的排序方法，时间复杂度接近于O(n)。 但，当待排序的关键字很多、n值较大时，此方法就不再适用。,13,9.2.3 希尔排序,希尔排序（shell sort）是D.希尔（D.L.Shell）提出的“缩小增量”
7、的排序方法。它的作法不是每次一个元素挨一个元素的比较，而是初期选用大跨步（增量较大）间隔比较，使记录跳跃式接近它的排序位置；然后增量缩小；最后增量为1，这样记录移动次数大大减少，提高了排序效率。希尔排序对增量序列的选择没有严格规定。,14,算法思路：,（1）先取一个正整数d1(d1 n)，把全部记录分成d1个组，所有距离为d1的倍数的记录看成一组。假设d1=4，那么记录共分4组： 第1组：r1,r5,r9,; 第2组：r2,r6,r10; 第3组：r3,r7,; 第4组：r4,r8,; 在各组内部进行插入排序，使得数据在每组内是有序的，但整个记录表仍然无序；,15,算法思路：,（1）先取一个正
8、整数d1(d1 =1)，所有记录成为一个大组为止。此时整个记录表有序，排序完成。 一般：选d1 约为n/2，d2 为d1 /2， d3为d2 /2，di=1。,16,例9.2,有一组关键字76，81，60，22，98，33，12，79，将其按由小到大的顺序排序。 这里n=8，取：d1 =4，d2=2，d3 =1，排序过程如图。,17,希尔排序-算法9.3,template void shell(T r ,int n) int i,j,k; k=n/2; /k值代表前文中的d值 while (k=1) /增量k的循环 for (i=k+1;ir0.key) /shell end,算法外层是增量由
9、n/2缩小到的循环。 for循环是针对某一特定的增量k，进行大跨步跳跃式地插入排序。,18,希尔排序-算法分析,当k=1时，此算法就等同于直接插入排序方法。由于前边大增量的处理，使关键字大体有序，速度快。 有人在大量实验基础上推出，它的时间复杂度约为O(n1.3)。 如果对关键字序列6,7,51,2,52,8进行希尔排序，可看出希尔排序是不稳定的。,19,9.3 交换排序,交换排序主要是根据记录的关键字的大小，将记录进行交换来排序的。 这里介绍两种交换排序方法： 冒泡排序和快速排序。 为了方便理解算法，本节使用数组时均从下标1开始。假设数组名是a，第一个数据元素放在a1 之中。,20,9.3.
10、1 冒泡排序,冒泡排序（Bubble Sort）是一种人们熟知、简单的交换排序方法。排序的算法思路如下： （1）让j取n变化至2： 将rj.key与rj1.key比较，如果rj.keyrj1.key，则记录rj与rj1交换，否则不交换。 最后是r2.key与r1.key对比，关键字较小的记录就换到r1的位置上，到此第一趟结束。 最小关键字的记录就像最轻的气泡冒到顶部一样换到了文件的前边。,21,冒泡排序,（2）让j取n变化至3，重复上述的比较对换操作，最终r2中存放的是剩余n1个记录(r1除外)中关键字最小的记录。 （3）让j取n至i+1，经过一系列对联对比交换后，ri中是剩余若干记录中关键字
11、最小的记录。 （4）让j取n至n1，将rn.key与rn1.key对比，把关键字较小的记录换到rn1中。 经过n1趟冒泡外理，rn中剩下的即是关键字最大的记录，到此排序完毕。,22,例9.3 有一组关键字44,55,22,33,99,11,66,77。,23,冒泡排序-算法9.4,template bubblesort(T r ,int n) int i=1, tag,j; T x; do tag=0; /数据交换标志 for (j=n; ji; j-) if (rj.keyrj-1.key) x=rj; rj=rj-1; rj-1=x; tag=1; i+; while (tag= =1 /
12、bubblesort,tag为标志变量，当某一趟处理过程中未进行过记录交换时tag值应为0；若发生过交换，则tag值为1。 所以外循环结束条件是：或者tag=0，已有序；或者i=n，已进行了n1趟处理。 用于教师口述！,24,冒泡排序-算法分析,冒泡排序算法的时间复杂度为O(n2)。 但，当原始关键字序列已有序时，只进行一趟比较就结束，时间复杂度为O(n)。 可以看出冒泡排序是稳定的。,25,9.3.2 快速排序,快速排序由霍尔（Hoare）提出，是对冒泡排序的改进。由于排序速度非常快，故称快速排序（Quick Sort）。 快速排序方法的实质是将一组关键字K1,K2,Kn进行分区交换排序。,
13、26,1. 快速排序算法思路,（1）以关键字K1为控制字，将K1,K2, Kn分成两子区，左区所有关键字小于等于K1，右区则大于等于K1，最后K1居两个子区中部。但在子区内数据尚处于无序状态。 （2）将右区首、尾指针（记录的下标号）保存入栈。对左区进行与第（1）步相类似处理，得到它的左、右子区，控制字居中。 （3）重复第（1）（2）步，直到左区处理完毕。然后退栈对一个个子区进行相类似的处理，直到栈空为止，即直到分区的大小为1为止。,27,例9.4,设有一组关键字46,56,14,43,95,19,18,72，这里n=8。试用快速排序方法由小到大进行排序。 第1趟，首先用两个指针i、j分别指向首
14、、尾两个关键字，i=1,j=8。第一个关键字46作为控制字，该关键字所属的记录另存储在一个x变量中。从文件右端元素rj.key开始与控制字x.key相比较，。重复上面的步骤，直到i=j，此处就是控制字x所在记录的位置。 将文件分成了左、右两个子区，具体如下页图。 然后将右边子文件的首、尾记录的下标进栈保存。 在针对左边子文件进行与上述方法相同的分区处理。见后面第2页图。,28,第1趟,建议教师在黑板上，边写画边讲！,29,继续进行快速排序，到完成。,教师注意：教材P276 图9.5有错，按下面矫正。,30,2 . 算法实现,由上例看出，快速排序算法总框架是进行多趟的分区处理； 而对某一特定子区
15、，则应把它看成又是一个待排序的文件，控制字总是取子区中第一个记录的关键字。 设计一个函数hoare()，它仅对某一待排序文件进行左、右子区的划分，使控制字居中； 另设计一个主体框架函数quicksort()，此多次调用hoare()函数，以实现对整个文件的排序。,31,（1）分区处理函数hoare()-算法9.5,template int hoare(T a ,int l,int h) int i,j; T x; i=l; j=h; x.key=ai.key; do while(i=x.key) j-; if(ij) ai.key=aj.key;i+; while(ij) / i是控制字的位置 /hoare end,设某区段文件， 指第1个记录的指针为l, 指最后一个记录的指针为h， 返回i 是控制字位置。,32,（2）快速排序主体框架算法,对一个待排序的文件，令l=1,h=n，调用hoare()，求出i； 然后右子区l=i+1,h=n，入栈。 对左子区令l=1,h=i1，再次调用hoare,，如此
