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

第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.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 *rcd; / 存储空间基址 int length; / 当前长度 int size; / 存储容量 RcdSqList; / 记录的顺序表 注意：顺序表的0号单元闲置或用作哨兵。 在后面的讨论中，前后文意思清楚的情况下，约定： 把“记录的关键字的大小”和“记录的关键字的比较”简称为“记录的大小”和“记录的比较”。 将“元素的关键字的大小”和“结点的关键字大小”简称为“元素的大小”和“结点的大小”。,3.1.2 排序的分类,根据在排序过程中涉及的存储器不同，可将排序方法分为两大类：内部排序和外部排序。 内部排序是指待排序列完全存放在内存中所进行的排序过程，适合不太大的元素序列。 外部排序指的是大文件的排序，待排序的文件无法一次装入内存，将待排序的记录存储在外存储器上，需要在内存和外部存储器之间进行多次数据交换，以达到排序整个文件的目的。,内部排序的分类,内部排序方法分为五类：交换排序、选择排序、插入排序、归并排序和基数排序。 其中交换排序、选择排序和插入排序是一个逐步扩大记录的有序序列长度的过程。,有序序列区,无 序 序 列 区,有序序列区,无 序 序 列 区,排序的介绍,交换排序是对无序区中记录的关键字两两进行比较，若逆序则交换，直到关键字之间不存在逆序为止。冒泡排序和快速排序是交换排序中最典型的两个方法。 选择排序是在无序区中选出关键字最小的记录，置于有序区的最后，直到全部记录有序。简单选择排序和堆排序是选择排序中最典型的两个方法。,2,1,3,4,5,2,1,3,4,5,排序的介绍,插入排序是将无序区中的一个记录插入至有序区，使得有序区的长度加1，直到全部记录有序。直接插入排序和希尔排序是插入排序中最具代表性的两个方法。 归并排序是不断将两个或两个以上有序区合并成一个有序区，直到全部记录有序。 基数排序是和前面所述各类排序方法完全不同的一种排序方法，不需要进行记录关键字的比较。,2,1,3,4,5,排序算法的时间复杂度分类,内部排序方法按时间复杂度分为三类： 简单的排序方法，时间复杂度为O(n2)； 先进的排序方法，时间复杂度为O(nlogn)； 基数排序，时间复杂度为O(n)。 希尔排序的算法时间复杂度与增量序列有关，还涉及到一些数学上尚未解决的难题，其算法时间复杂度不属于以上类别。 每一种排序方法都有各自的优缺点，适合于不同的应用场合。 为方便起见，若非特意强调，排序的实施均为非递减有序排序。,直接插入排序,假如8个记录的关键字序列为（56, 68, 25, 45, 90, 38, 10, 72）,每一趟的排序过程可参看下图： 第i趟插入排序将记录L.rcdi+1插入到有序区L.rcd1i中，插入前需要找到插入位置，移动记录空出插入位置。,45,45,68,90,算法实现分析,查找插入位置 从有序区的位置1到i，判断是否为记录L.rcdi+1的插入位置j，代码为： j = 1; while (L.rcdj.keyj) L.rcdk+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,直接插入排序算法性能分析,排序算法的时间耗费主要与关键字比较和记录移动的次数相关。 最好的情况（关键字在记录序列中顺序有序）,“比较”的次数：,“比较”的次数：,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,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, 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 ），序列已基本有序，接近最好情况（微观调整）的直接插入排序。 可将前面各趟的“宏观”调整看成是最后一趟的预处理，实现比只做一次直接插入排序效率更高。,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-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 多关键字排序,一般情况下，多关键字排序的定义为：假设含有 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进行排序，致使k1值相同的记录构成长度更短的子序列； 依次重复，直至就当前得到的各个子序列按km-1 进行从小到大进行排序； 最后由这些子序列依次相连所得序列便是排序的最后结果。 低位优先排序 先按最低位关键字进行排序 ； 接着按次低位关键字实施排序 ； 最后按最主位关键字进行排序。 与高位优先排序不同，其排序过程中不产生子序列，每趟都是对整个序列进行排序。,实例,现需要学生实施多关键字的排序，其中年级、班别和学号为关键字序列，且年级为最主位关键字。 若采用低位优先排序法，先按学号进行排序 接着按班别进行排序 最后按年级进行排序 低位优先排序必须使用稳定的排序算法,黄红,张晗,4,4,4,4,黄红,张晗,基数排序,将记录的关键字看成由m个关键字复合而成，每个关键字可能取r个值，则只要从最低位关键字起，先按关键字的不同值将记录“分配”到r个子序列，再按从小到大将各子序列依次首尾相接“收集”在一起，如此重复m趟，最终完成整个记录序列的排序。按这种方法实现的排序称为基数排序。 假设关键字k是十进制数，即r=10，且其值都在0到999的范围内，则可把k中的每一位数字看成一个关键字，即认为k由三个关键字（k0, k1, k2）组成，其中k0是个位数，k1是十位数，k2是百位数。 若关键字k是字符串，则可把字符串中的每一个字母看成一个关键字，即r = 26。,基数排序的实现方法,链式基数排序在链式存储结构中实现。在每一趟排序中，分配是按相应关键字的取值将记录加入到r个不同的队列；收集是从小到大依次将r个队列首尾相接成一个链表。 计数基数排序在顺序存储结构中实现。在每一趟排序中，分配是对相应关键字的每种取值计数（即统计r个子序列的长度），确定每个子序列的起始位置；收集是根据各子序列的起始位置将记录复制到合适位置。,计数基数排序,数据类型定义 typedef struct KeysType *keys; / 关键字 / 其它数据项 KeysRcdType; / 基数排序中的记录类型 typedef struct KeysRcdType *rcd; / 0号位置空闲 int length; / 顺序表长度 int size; / 顺序表容量 int digitNum; / 关键字位数 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个记录序列需进行三趟“分配”和“收集”完成低位优先的计数基数排序。 第一趟对个位数排序，首先用数组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,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,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,pos,rcd,第三趟分配与收集,第三趟对数组rcd进行分配 第三趟收集，将记录从数组rcd收集到rcd1 由于趟数为奇数，需将数组rcd1复制回rcd