数据结构ppt 2016ppt 第3章

1、第3章 排序基础,广东工业大学 计算机学院,数据结构,3.1 排序的概念与分类 3.1.1 排序的概念 3.1.2 排序的分类 3.2 直接插入排序 3.3 希尔排序 3.4 基数排序 3.4.1 多关键字排序 3.4.2 基数排序,第3章 排序基础,3.1 排序的概念与分类,含有多个数据项的数据元素称为记录。 用作记录唯一标识的数据项称为关键字域，其值称为关键字 。 若关键字唯一标识一个记录，则称为主关键字，否则为次关键字。 为了与元素类型ElemType区别，记录类型定义为RecordType。 typedef int KeyType; / 关键字类型为整数类型 typedef struc

2、t KeyType key; / 关键字项 / 其它数据项 RecordType, RcdType; / 记录类型,3.1.1 排序的概念,排序是将一组“无序”的记录序列调整为“有序”的记录序列的一种操作。 例如，将下列关键字序列： （175, 85, 260, 63, 412, 504, 840, 518, 630, 950） 调整为有序序列： （63, 85, 175, 260, 412, 504, 518, 630, 840, 950）,什么是排序,假设含n个记录的序列为（r1, r2, , rn） 其相应的关键字序列为 （k1, k2, , kn） 这些关键字相互之间可以进行比较，即在

3、它们之间存在着这样一个关系 kp1kp2kpn 按此固有关系将上式记录序列重新排列为 （rp1, rp2, ，rpn ） 的操作称作排序。,记录顺序表的类型定义,typedef struct RcdType *rcd; / 存储空间基址 int length; / 当前长度 int size; / 存储容量 RcdSqList; / 记录的顺序表 注意：顺序表的0号单元闲置或用作哨兵。 在后面的讨论中，前后文意思清楚的情况下，约定： 把“记录的关键字的大小”和“记录的关键字的比较”简称为“记录的大小”和“记录的比较”。 将“元素的关键字的大小”和“结点的关键字大小”简称为“元素的大小”和“结点

4、的大小”。,3.1.2 排序的分类,根据在排序过程中涉及的存储器不同，可将排序方法分为两大类：内部排序和外部排序。 内部排序是指待排序列完全存放在内存中所进行的排序过程。 外部排序是对大文件的排序，待排序的文件无法一次装入内存，在排序过程中需要在内存和外部存储器之间进行多次数据交换 。,内部排序的分类,内部排序方法分为五类：交换排序、选择排序、插入排序、归并排序和基数排序。 其中交换排序、选择排序和插入排序是一个逐步扩大记录的有序序列长度的过程。,有序序列区,无 序 序 列 区,有序序列区,无 序 序 列 区,排序的介绍,交换排序是对无序区中记录的关键字两两进行比较，若逆序则交换，直到关键字之

5、间不存在逆序为止。冒泡排序和快速排序是交换排序中最典型的两个方法。 选择排序是在无序区中选出关键字最小的记录，置于有序区的最后，直到全部记录有序。简单选择排序和堆排序是选择排序中最典型的两个方法。,2,1,3,4,5,2,1,3,4,5,排序的介绍,插入排序是将无序区中的一个记录插入至有序区，使得有序区的长度加1，直到全部记录有序。直接插入排序和希尔排序是插入排序中最具代表性的两个方法。 归并排序是不断将两个或两个以上有序区合并成一个有序区，直到全部记录有序。 基数排序是和前面所述各类排序方法完全不同的一种排序方法，不需要进行记录关键字的比较。,2,1,3,4,5,排序算法的时间复杂度分类,内

6、部排序方法按时间复杂度分为三类： 简单的排序方法，时间复杂度为O(n2)； 先进的排序方法，时间复杂度为O(nlogn)； 基数排序，时间复杂度为O(n)。 希尔排序的算法时间复杂度与增量序列有关，还涉及到一些数学上尚未解决的难题，其算法时间复杂度不属于以上类别。 每一种排序方法都有各自的优缺点，适合于不同的应用场合。 为方便起见，若非特意强调，排序的实施均为非递减有序（升序）排序。,直接插入排序,假如8个记录的关键字序列为（56, 68, 25, 45, 90, 38, 10, 72）,每一趟的排序过程可参看下图： 第i趟插入排序将记录L.rcdi+1插入到有序区L.rcd1.i中，插入前需

7、要找到插入位置，移动记录空出插入位置。,45,45,68,90,13,直接插入排序,利用 “顺序查找”实现 “在R1.i-1中查找Ri的插入位置”,算法的实现要点：,14,从Ri-1起向前进行顺序查找， 监视哨设置在R0；,R0 = Ri; / 设置“哨兵”,循环结束表明Ri的插入位置为 j +1,R0,j,Ri,for (j=i-1; R0.keyRj.key; -j); / 从后往前找,j=i-1,插入位置,15,对于在查找过程中找到的那些关键字不小于Ri.key的记录，并在查找的同时实现记录向后移动；,for (j=i-1; R0.keyRj.key; -j); Rj+1 = Rj,R0

8、,j,Ri,j= i-1,上述循环结束后可以直接进行“插入”,插入位置,16,令 i = 2，3，, n, 实现整个序列的排序。,for ( i=2; i=n; +i ) if (Ri.keyRi-1.key) 在 R1.i-1中查找Ri的插入位置; 插入Ri ; ,17,void InsertionSort ( RcdSqList +i ) if (L.rcdi.key L.rcdi-1.key) / InsertSort,L.rcd0 = L.rcdi; / 复制为监视哨 for (j=i-1; L.rcd0.key L.rcdj.key; - j) L.rcdj+1 = L.rcdj;

9、/ 记录后移 L.rcdj+1 = L.rcd0; / 插入到正确位置,算法实现分析(书本上的实现),查找插入位置 从有序区的位置1到i，判断是否为记录L.rcdi+1的插入位置j，代码为： j = 0; do j+; while (L.rcdj.keyj); / 从后到前移动记录 若将判断插入位置的次序改为从i到1，则可将上述两步的代码合并为： L.rcd0 = L.rcdi+1; j = i+1; do j-;L.rcdj+1 = L.rcdj;while(j1 / 从后到前查找并移动记录 0号单元存放了记录L.rcdi+1，判断j是否越界的操作“j1”可以略去。L.rcd0起到了边界监视

10、哨的作用，称为哨兵。,直接插入排序,void InsertSort (RcdSqList / 关键字 / 其它数据项 KeysRcdType; / 基数排序中的记录类型 typedef struct KeysRcdType *rcd; / 0号位置做哨兵 int length; / 顺序表长度 int size; / 顺序表容量 int digitNum; / 关键字位数 int radix; / 关键字基数 KeysSqList; / 顺序表类型,计数基数排序的实现,引入三个数组 数组count用于统计关键字的r种取值的个数。counti是对值i的计数； 数组pos用于确定各子序列的起始位置

11、。posi是值为i的子序列的起始位置。 数组rcd1与rcd类型相同。在各趟收集中，第一趟从数组rcd收集到rcd1，第二趟从rcd1收集到rcd，如此交替进行，若总趟数为奇数，最后还需将排序结果从数组rcd1复制回rcd。,举例,对关键字为（337, 332, 132, 267, 262, 164, 260, 167）的8个记录序列需进行三趟“分配”和“收集”完成低位优先的计数基数排序。 第一趟对个位数排序，首先用数组count对个位数的每种取值计数，共有1个0、3个2、1个4和3个7，其余均为0个。 利用count数组统计第i个关键字各种取值的个数： for(j=0; jL.radix;

12、+j) countj = 0; / 初始化 for(k=1; k=n; k+) countrcdk.keysi+; / 对各种取值计数,7,0,0,0,0,1,2,1,2,2,7,2,3,4,1,0,1,7,3,2,举例,利用count数组的结果，依次计算个位数从0到9的关键字存储的起始位置，存入数组pos。 pos0 = 1; for(j=1; jL.radix; +j) posj = posj-1+countj-1;,1,2,2,5,5,6,6,6,9,9,count0,count1,count2,count9,pos0=1,pos2= pos1+count1,pos9= pos8+cou

13、nt8,=pos0+count0,pos1,举例,第一趟收集 由337的个位数7取得其起始位置pos7的值6，将337放入rcd16中，并将pos7加1，令pos7指向下一个个位数为7的记录应放入的位置。 由332的个位数2取得其起始位置pos2的值2，将332放入rcd12中，并将pos2加1。 收集的代码 for(k=1; k=n; +k) / 收集 j = rcdk.keysi; rcd1posj+ = rcdk; / 复制记录,对应的起始位置加1 ,2,5,6,7,8,9,3,4,5,6,1,2,2,5,6,6,9,9,3 3 7,3 3 2,1 6 7,2 6 0,1 6 4,2 6

14、 2,2 6 7,1 3 2,rcd,pos,rcd1,3 3 7,3 3 2,1 3 2,2 6 7,2 6 2,1 6 4,2 6 0,1 6 7,第二趟分配与收集,第二趟对数组rcd1进行分配 第二趟收集，将记录从数组rcd1收集到rcd,4,1,6,6,6,6,6,3,3,3,0,0,3,5,rcd1,2 6 0,1 3 2,2,5,8,3 3 2,2 6 2,1 6 4,6,3 3 7,3,4,7,2 6 7,9,1 6 7,1,1,1,4,4,9,9,9,count,pos,rcd,第三趟分配与收集,第三趟对数组rcd进行分配 第三趟收集，将记录从数组rcd收集到rcd1 由于趟数

15、为奇数，需将数组rcd1复制回rcd。,9,0,0,1,1,1,3,2,2,2,3,3,3,2,0,1,1,4,7,9,9,9,9,9,9,3 3 2,1 6 7,8,rcd,1 3 2,2,3 3 7,4,2 6 0,5,2 6 2,6,1 6 4,3,2 6 7,7,count,pos,rcd1,一趟计数基数排序,void RadixPass(KeysRcdType rcd, KeysRcdType rcd1, int n, int i, int count, int pos, int radix) int k, j; for(k=1; k=n; k+) countrcdk.keysi+; / 对各种取值计数 pos0 = 1; for(j=1; jradix; +j) posj = countj-1+posj-1; / 求起始位置 for(k=1; k=n; +k) / 收集 j = rcdk.keysi; rcd1posj+ = rcdk; / 复制记录，对应的起始位置加1 ,计数基数排序的算法,Status RadixSort(KeysSq