算法设计与分析-蛮力思想.ppt

《算法设计与分析-蛮力思想.ppt》由会员分享，可在线阅读，更多相关《算法设计与分析-蛮力思想.ppt（40页珍藏版）》请在三一办公上搜索。

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 struct KeyType key;/关键字项/其它数据项 RecordType,RcdType;/记录类型,3.1.

2、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）这些关键字相互之间可以进行比较，即在它们之间存在着这样一个关系 kp1kp2kpn按此固有关系将上式记录序列重新排列为（rp1,rp2,，rpn）的操作称作排序。,记录顺序表的类型定义,typedef struct RcdType*rc

3、d;/存储空间基址 int length;/当前长度 int size;/存储容量 RcdSqList;/记录的顺序表注意：顺序表的0号单元闲置或用作哨兵。在后面的讨论中，前后文意思清楚的情况下，约定：把“记录的关键字的大小”和“记录的关键字的比较”简称为“记录的大小”和“记录的比较”。将“元素的关键字的大小”和“结点的关键字大小”简称为“元素的大小”和“结点的大小”。,3.1.2 排序的分类,根据在排序过程中涉及的存储器不同，可将排序方法分为两大类：内部排序和外部排序。内部排序是指待排序列完全存放在内存中所进行的排序过程，适合不太大的元素序列。外部排序指的是大文件的排序，待排序的文件无法一次

4、装入内存，将待排序的记录存储在外存储器上，需要在内存和外部存储器之间进行多次数据交换，以达到排序整个文件的目的。,内部排序的分类,内部排序方法分为五类：交换排序、选择排序、插入排序、归并排序和基数排序。其中交换排序、选择排序和插入排序是一个逐步扩大记录的有序序列长度的过程。,有序序列区,无 序 序 列 区,有序序列区,无 序 序 列 区,排序的介绍,交换排序是对无序区中记录的关键字两两进行比较，若逆序则交换，直到关键字之间不存在逆序为止。冒泡排序和快速排序是交换排序中最典型的两个方法。选择排序是在无序区中选出关键字最小的记录，置于有序区的最后，直到全部记录有序。简单选择排序和堆排序是选择排序中

5、最典型的两个方法。,2,1,3,4,5,2,1,3,4,5,排序的介绍,插入排序是将无序区中的一个记录插入至有序区，使得有序区的长度加1，直到全部记录有序。直接插入排序和希尔排序是插入排序中最具代表性的两个方法。归并排序是不断将两个或两个以上有序区合并成一个有序区，直到全部记录有序。基数排序是和前面所述各类排序方法完全不同的一种排序方法，不需要进行记录关键字的比较。,2,1,3,4,5,排序算法的时间复杂度分类,内部排序方法按时间复杂度分为三类：简单的排序方法，时间复杂度为O(n2)；先进的排序方法，时间复杂度为O(nlogn)；基数排序，时间复杂度为O(n)。希尔排序的算法时间复杂度与增量序

6、列有关，还涉及到一些数学上尚未解决的难题，其算法时间复杂度不属于以上类别。每一种排序方法都有各自的优缺点，适合于不同的应用场合。为方便起见，若非特意强调，排序的实施均为非递减有序排序。,直接插入排序,假如8个记录的关键字序列为（56,68,25,45,90,38,10,72）,每一趟的排序过程可参看下图：第i趟插入排序将记录L.rcdi+1插入到有序区L.rcd1.i中，插入前需要找到插入位置，移动记录空出插入位置。,45,45,68,90,算法实现分析,查找插入位置从有序区的位置1到i，判断是否为记录L.rcdi+1的插入位置j，代码为：j=1;while(L.rcdj.keyj)L.rcd

7、k+1=L.rcdk;k-;/从后到前移动记录若将判断插入位置的次序改为从i到1，则可将上述两步的代码合并为：L.rcd0=L.rcdi+1;j=i;while(j0/从后到前查找并移动记录0号单元存放了记录L.rcdi+1，判断j是否越界的操作“j0”可以略去。L.rcd0起到了边界监视哨的作用，称为哨兵。,直接插入排序,void InsertSort(RcdSqList&L),设置哨兵 查找插入位置，移动记录空出插入位置 插入记录,void InsertSort(RcdSqList/插入,0,38,1,j,i,i+1,25,45,56,68,90,10,72,38,38,直接插入排序算法性

8、能分析,排序算法的时间耗费主要与关键字比较和记录移动的次数相关。最好的情况（关键字在记录序列中顺序有序）,“比较”的次数：,“比较”的次数：,0,“移动”的次数：,“移动”的次数：,直接插入排序的最好情况下时间复杂度为O(n)，最坏情况下时间复杂度为O(n2)。,最坏的情况（关键字在记录序列中逆序有序）,直接插入排序只需要一个记录的辅助空间，其空间复杂度为O(1)。,希尔排序,希尔排序是将整个待排记录序列（R1,R2,R3,Rn）按增量d划分成d个子序列，其中第i（1id）个子序列为（Ri,Ri+d,Ri+2d,Ri+kd）,13,55,38,76,27,04,65,49,49,97,1,2,

9、3,4,5,6,7,8,9,10,3.3 希尔排序,分别对各子序列进行直接插入排序；不断减小增量d，重复这一过程；直到d减少到1，对整个序列进行一次直接插入排序。增量d的取值序列称为增量序列。基于增量序列的降序特点，希尔排序也被称为“缩小增量排序”。,希尔排序实例,待排序列（49,38,65,97,76,13,27,49,55,04）第一趟排序的增量d1为5 结果为（13,27,49,55,04,49,38,65,97,76）,13,49,27,38,65,49,97,55,76,04,1,2,3,4,5,6,7,8,9,10,希尔排序实例,第二趟希尔排序的增量d2为3结果为（13,04,49

10、,38,27,49,55,65,97,76）第三趟的增量d3为1，最后结果为（04,13,27,38,49,49,55,65,76,97）,13,55,38,76,27,04,65,49,49,97,1,2,3,4,5,6,7,8,9,10,希尔排序与直接插入排序,直接插入排序每次对相邻记录进行比较，记录最多只移动了一个位置，希尔排序每次对相隔较远距离（即增量）的记录进行比较，使得记录移动时能跨过多个记录，实现宏观上的调整。希尔排序的最后一趟排序（增量为1），序列已基本有序，接近最好情况（微观调整）的直接插入排序。可将前面各趟的“宏观”调整看成是最后一趟的预处理，实现比只做一次直接插入排序效率

11、更高。,void ShellInsert(RcdSqList/插入,一趟希尔排序,void ShellInsert(RcdSqList&L,int dk),暂存待插入记录 按增量dk查找插入位置,移动记录空出插入位置 插入记录,0,49,i-3,j,i,i+3,13,04,49,55,27,65,38,97,76,38,38,希尔排序,void ShellSort(RcdSqList/一趟增量为dk的插入排序,希尔排序的时间复杂度分析,希尔排序的时间复杂度分析是一个复杂的问题，因为它的时间复杂度是所取增量序列的函数，这涉及到一些数学上尚未解决的难题。有研究指出，当增量序列为dk=2t-k+1-

12、1时，希尔排序的时间复杂度为O(n1.5)，其中t为排序趟数，1ktlog2(n+1)。,排序的稳定性,假设ki=kj(1in,1jn,ij)，且在排序前的序列中ki领先于kj(即i j)。若在排序后的序列中ki仍领先于kj，则称所用的排序方法是稳定的；否则，排序方法是不稳定的。从希尔排序的例子可见，序列有两个49，后一个49在排序后排到了49前面，因此希尔排序是不稳定的排序算法。,3.4 基数排序,前面介绍的排序方法都基于关键字比较，而基数排序不需要比较关键字。基数排序借鉴多关键字排序的思想，把关键字看成由多个关键字复合而成。,3.4.1 多关键字排序,一般情况下，多关键字排序的定义为：假设

13、含有 n 个记录的序列为（r1,r2,rn）每个记录ri含有 m 个关键字（ki0，ki1，kim-1），如果对于序列中任意两个记录ri 和rj（1ijn）都满足下列有序关系：（ki0，ki1，kim-1）（kj0，kj1，kjm-1）则称记录序列对这m个关键字有序。其中k0被称作最主位关键字，km-1被称作最次位关键字；(a0,a1,am-1)(b0,b1,bm-1)是指必定存在l，使得：当s=0,l-1时，as=bs，而albl。,实现多关键字排序策略,高位优先排序先按最主位关键字k0进行排序，得到若干子序列，其中每个子序列中的记录都含相同的k0值；接着分别就每个子序列按关键字k1进行排序

14、，致使k1值相同的记录构成长度更短的子序列；依次重复，直至就当前得到的各个子序列按km-1 进行从小到大进行排序；最后由这些子序列依次相连所得序列便是排序的最后结果。低位优先排序先按最低位关键字进行排序；接着按次低位关键字实施排序；最后按最主位关键字进行排序。与高位优先排序不同，其排序过程中不产生子序列，每趟都是对整个序列进行排序。,实例,现需要学生实施多关键字的排序，其中年级、班别和学号为关键字序列，且年级为最主位关键字。若采用低位优先排序法，先按学号进行排序接着按班别进行排序最后按年级进行排序低位优先排序必须使用稳定的排序算法,黄红,张晗,4,4,4,4,黄红,张晗,基数排序,将记录的关键

15、字看成由m个关键字复合而成，每个关键字可能取r个值，则只要从最低位关键字起，先按关键字的不同值将记录“分配”到r个子序列，再按从小到大将各子序列依次首尾相接“收集”在一起，如此重复m趟，最终完成整个记录序列的排序。按这种方法实现的排序称为基数排序。假设关键字k是十进制数，即r=10，且其值都在0到999的范围内，则可把k中的每一位数字看成一个关键字，即认为k由三个关键字（k0,k1,k2）组成，其中k0是个位数，k1是十位数，k2是百位数。若关键字k是字符串，则可把字符串中的每一个字母看成一个关键字，即r=26。,基数排序的实现方法,链式基数排序在链式存储结构中实现。在每一趟排序中，分配是按相

16、应关键字的取值将记录加入到r个不同的队列；收集是从小到大依次将r个队列首尾相接成一个链表。计数基数排序在顺序存储结构中实现。在每一趟排序中，分配是对相应关键字的每种取值计数（即统计r个子序列的长度），确定每个子序列的起始位置；收集是根据各子序列的起始位置将记录复制到合适位置。,计数基数排序,数据类型定义typedef struct KeysType*keys;/关键字/其它数据项 KeysRcdType;/基数排序中的记录类型typedef struct KeysRcdType*rcd;/0号位置空闲int length;/顺序表长度int size;/顺序表容量int digitNum;/关

17、键字位数int radix;/关键字基数 KeysSqList;/顺序表类型,计数基数排序的实现,引入三个数组数组count用于统计关键字的r种取值的个数。counti是对值i的计数；数组pos用于确定各子序列的起始位置。posi是值为i的子序列的起始位置。数组rcd1与rcd类型相同。在各趟收集中，第一趟从数组rcd收集到rcd1，第二趟从rcd1收集到rcd，如此交替进行，若总趟数为奇数，最后还需将排序结果从数组rcd1复制回rcd。,举例,对关键字为（337,332,132,267,262,164,260,167）的8个记录序列需进行三趟“分配”和“收集”完成低位优先的计数基数排序。第一

18、趟对个位数排序，首先用数组count对个位数的每种取值计数，共有1个0、3个2、1个4和3个7，其余均为0个。利用count数组统计第i个关键字各种取值的个数：for(j=0;jL.radix;+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,

19、6,6,6,9,9,count0,count1,count2,count9,pos0=1,pos2=pos1+count1,pos9=pos8+count8,=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,

20、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 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,

21、pos,rcd,第三趟分配与收集,第三趟对数组rcd进行分配第三趟收集，将记录从数组rcd收集到rcd1由于趟数为奇数，需将数组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 ra

22、dix)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(KeysSqList,计数基数排序的性能分析,计数基数排序算法无需比较关键字，主要操作是分配和收集。对于n个记录，每个记录包含m个关键字，基数为r，分配过程统计r个值对应的记录数，收集过程根据统计的结果将记录复制到合适位置。因此一趟分配与收集的时间复杂度为O(n)。记录由m个关键字构成，则需要进行m趟分配与收集，因此时间复杂度为O(mn)。计数基数排序算法是一种稳定的排序算法。通常m远小于n，时间复杂度可视为O(n)。由于采用了长度为n的辅助数组rcd1，算法的空间复杂度为O(n)。,