数据结构课件第十章内部排序.ppt

数据结构-第十章 内部排序,1,第十章 内部排序,10.1 概述10.2 插入排序10.3 交换排序10.4 选择排序10.5 归并排序10.6 基数排序10.7 各种内部排序方法比较本章学习要点 习题与上机作业,数据结构-第十章 内部排序,2,10.1 概述,10.1.1 什么是排序 其目的是将一组“无序”的记录序列调整为“有序”的记录序列，是根据记录关键字的值的非递减或者非递增（递增或者递减）的关系将文件记录的次序重新排列。,例 将下列关键字序列：52,49,80,36,14,58,61,23,97,75 调整为：14,23,36,49,52,58,61,75,80,97,数据结构-第十章 内部排序,3,10.1.2 排序的分类,根据排序时文件记录的存放位置 内部排序：排序过程中将全部记录放在内存中处理。外部排序：排序过程中需在内外存之间交换信息。根据排序前后相同关键字记录的相对次序 稳定排序：设文件中任意两个记录的关键字值相同，即Ki=Kj(ij)，若排序之前记录Ri领先于记录Rj，排序后这种关系不变(对所有输入实例而言)。不稳定排序：只要有一个实例使排序算法不满足稳定性要求。,数据结构-第十章 内部排序,4,根据文件的存储结构划分排序的种类 顺序存储 链式存储 地址存储:待排记录顺序存储，排序时只对辅助 表(关键字+指针)的表目进行物理重排。根据内部排序的方法 插入排序 交换排序 选择排序 归并排序 基数排序根据排序算法所需的辅助空间 就地排序：O(1)非就地排序：O(n)或与n有关,数据结构-第十章 内部排序,5,内部排序的过程是一个逐步扩大记录的有序序列长度的过程。,内部排序方法基于不同的“扩大”有序序列长度的方法。,数据结构-第十章 内部排序,6,10.1.3 评价排序算法的主要标准,时间开销 考察算法的两个基本操作的次数：比较关键字移动记录 算法时间还与输入实例的初始状态有关时，分情况：最好最坏平均空间开销 所需的辅助空间,数据结构-第十章 内部排序,7,讨论约定(1)顺序存储(2)按记录关键字非递减，关键字为整数,#define MAXSIZE 20typedef int KeyType;typedef struct KeyType key;InfoType otherinfo;RedType;typedef structRedType rMAXSIZE+1;/r0闲置或作哨兵int length;SqList;,0 1 2 L.length MAXSIZE,SqList L；,L.r,数据结构-第十章 内部排序,8,10.2 插入排序,有序序列R1.i-1,Ri,无序序列 Ri.n,一趟直接插入排序的基本思想：,有序序列R1.i,无序序列 Ri+1.n,不同的具体实现方法导致不同的算法描述：直接插入排序（基于顺序查找）折半插入排序（基于折半查找）表插入排序（基于链表存储）希尔排序（基于逐趟缩小增量）,数据结构-第十章 内部排序,9,10.2.1 直接插入排序（增量法）利用“顺序查找”实现“在R1.i-1中查找Ri的插入位置”示例 R(0)R(-4)R(8)R(1)R(-4)R(-6)n=6 i=1 0-4 8 1-4-6 i=2-4 0 8 1-4-6 i=3-4 0 8 1-4-6 i=4-4 0 1 8-4-6 i=5-4-4 0 1 8-6 i=6-6-4-4 0 1 8 算法思想 每次使有序区增加一个记录,稳定排序,数据结构-第十章 内部排序,10,算法步骤,0 1 i-1 i i+1 nr0.n ri(有序区)(无序区)循环(n-1)次，初值 i=21)若riri-1，则把第i个记录取出保存在r0中，j=i-1 2)若r0 rj，则rj后移一位，j=j-1，转2)；否则r0放在rj+1处，i=i+1，转1)算法描述,void InsertSort(SqList/InsertSort,数据结构-第十章 内部排序,11,哨兵/监视哨的作用,简化边界条件的测试，提高算法时间效率。性能分析最好情况(原始数据按正序即非递减序排列)Cmin=Mmin=0最坏情况(原始数据按逆序即非递增序排列)Cmax=Mmax=随机情况 Cavg=(Cmin+Cmax)/2n2/4 Mavg n2/4时间复杂度O(n2)辅助空间复杂度O(1),数据结构-第十章 内部排序,12,改进措施,折半插入排序 算法思想：将循环中每一次在区间 1,i-1 上为确定插入位置的顺序查找操作改为折半查找操作。效果：减少关键字间的比较次数。2-路插入排序 算法思想：设置与r同样大小的辅助空间d，将r1赋值给d1，将d看作循环向量。对于ri(2in)，若rid1，则插入d1之后的有序序列中，反之则插入d1之前的有序序列中。(避免r1关键字最小/最大)效果：减少记录的移动次数。表插入排序 算法思想：构造静态链表，用改变指针来代替移动记录操作 效果：减少记录的移动次数。,d,r1,数据结构-第十章 内部排序,13,10.2.2 希尔排序(渐减/缩小增量排序),算法思想的出发点直接插入排序在待排序列的关键字基本有序时，效率较高在待排序的记录个数较少时，效率较高算法思想 先选定一个记录下标的增量d，将整个记录序列按增量d从第一个记录开始划分为若干组，对每组使用直接插入排序的方法；然后减小增量d，不断重复上述过程，如此下去，直到d=1(此时整个序列是一组)。,对待排记录序列先作“宏观”调整，再作“微观”调整。,数据结构-第十章 内部排序,14,示例,46 82 52 40 67 31 40 73 53 76 d1=5 31 46 40 82 52 73 40 53 67 76,不稳定排序,31 40 52 40 67 46 82 73 53 76,d2=3 31 40 76 82 40 67 73 46 52 53,31 40 46 40 67 52 76 73 53 82,d3=1 31 40 40 46 52 53 67 73 76 82,数据结构-第十章 内部排序,15,void ShellSort(SqList/ShellSort,算法描述,数据结构-第十章 内部排序,16,性能分析,时间复杂度是n和d的函数如何选择最佳d序列，目前尚未解决最后一个增量值必须为1避免增量序列中的值（尤其是相邻的值）有公因子实验结果：当n较大时，比较和移动次数约在n1.25到1.6n1.25。就地排序,数据结构-第十章 内部排序,17,10.3 交换排序,10.3.1 起泡排序(冒泡排序)算法思想 将两个相邻记录的关键字进行比较，若为逆序则交换两者位置，小者往上浮，大者往下沉。算法步骤 记录1和2、2和3、(n-1)和n的关键字比较(交换)；记录1和2、2和3、(n-2)和(n-1)的关键字比较(交换)；直到某一趟不出现交换操作为止。,数据结构-第十章 内部排序,18,示例,0-4-4-6-6-4 0-6-4-4 8-6-4-4-4-6-4 0 0 0-4 1 1 1 1 1 8 8 8 8 sorted F F F T,稳定排序,数据结构-第十章 内部排序,19,void BubbleSort(SqList/BubbleSort,算法描述,数据结构-第十章 内部排序,20,性能分析,最好情况(原始数据按正序即非递减序排列)Cmin=n-1 Mmin=0最坏情况(原始数据按逆序即非递增序排列)Cmax=Mmax=时间复杂度O(n2)辅助空间复杂度O(1)算法的改进每趟排序中，记录最后一次发生交换的位置双向交替扫描，下上，最轻升顶；上下，最重沉底,数据结构-第十章 内部排序,21,10.3.2 快速排序(分划交换排序/分治法),分治算法原理1)分解：将原问题分解为若干子问题2)求解：递归地解各子问题，若子问题的规模足够小，则直接求解3)组合：将各子问题的解组合成原问题的解快速排序算法思想 指定枢轴/支点/基准记录rp(通常为第一个记录)，通过一趟排序将其放在正确的位置上，它把待排记录分割为独立的两部分，使得 左边记录的关键字 rp.key 右边记录的关键字 对左右两部分记录序列重复上述过程，依次类推，直到子序列中只剩下一个记录或不含记录为止。(可以用递归方法实现),数据结构-第十章 内部排序,22,一趟快速排序示例,(49)38 65 97 76 13 27 49 i j 27 38 65 97 76 13()49 i j 27 38()97 76 13 65 49 i j 27 38 13 97 76()65 49 i j 27 38 13()76 97 65 49 i j 27 38 13 49 76 97 65 49,(i=j),0 1 2 3 4 5 6 7 8,49,数据结构-第十章 内部排序,23,算法描述,void QuickSort(SqList/QuickSort,void QSort(SqList Qsort(L,pivotloc+1,high)/QSort,数据结构-第十章 内部排序,24,算法描述（续）,int Partition(SqList/Partition,数据结构-第十章 内部排序,25,性能分析,最坏情况(原始数据正/逆序排列)Cmax=(n-1)+(n-2)+1=n(n-1)/2 Mmax Cmin O(n2)最好情况：每次划分的结果是基准的左、右两个无序子区间的长度大致相等 Cmin O(nlgn)Mmin Cmin O(nlog2n)平均时间性能 Tavg(n)=kn ln(n)k：某个常数；n：待排序序列中记录个数 就平均时间而言，快速排序是目前被认为最好的一种内部排序方法。辅助空间复杂度 最好情况 O(log2 n)最坏情况 O(n),L,L/2,L/2,L,1,1,1,数据结构-第十章 内部排序,26,算法的改进 合理选择枢轴记录可改善性能。例如，三者取中随机产生算法的稳定性 是非稳定排序 反例 2，2，1：1 2 2,思考：在链表存储结构上如何实现快速排序？,数据结构-第十章 内部排序,27,10.4 选择排序,10.4.1 简单选择排序(直接选择排序)算法思想 每次从待排序列中选出关键字最小记录作为有序序列中最后一个记录，直至最后一个记录为止。示例（n=8）,49 38 65 97 76 49 13 27 13 38 65 97 76 49 49 27 13 27 65 97 76 49 49 38 13 27 38 97 76 49 49 65 13 27 38 49 76 97 49 65 13 27 38 49 49 97 76 65 13 27 38 49 49 65 76 97 13 27 38 49 49 65 76 97（每趟排序使有序区增加一个记录）,不稳定排序,数据结构-第十章 内部排序,28,算法描述,void SelectSort(SqList/SelectSort,性能分析总的比较次数与记录排列的初始状态无关 C=(n-1)+(n-2)+.+2+1=n(n-1)/2移动次数 初始记录逆序时：Mmax=3(n-1)初始记录正序时：Mmin=0平均时间复杂度O(n2)辅助空间复杂度O(1),简单选择排序记录移动次数少,数据结构-第十章 内部排序,29,10.4.2 树形选择排序(锦标赛排序),算法思想 锦标赛名次产生过程。较简单选择排序减少“比较”次数。示例 23 23 40 38 23 40 46 38 23 38 40 性能 除第一次外，每次都走了树的一条分支，故其时间复杂度为 O(n log2 n)。缺陷 辅助空间较多；需与“最大值”进行多余的比较,23,38,38,38,38,46,38,38,38,46,40,40,46,46,稳定排序,数据结构-第十章 内部排序,30,10.4.3 堆排序,特点较直接选择排序减少重复比较；较树形选择排序减少辅助存储空间(仅需一个)(二叉)堆的定义 n个关键字的序列（k1,k2,.,kn）当且仅当满足下列条件之一：(1)KiK2i 且 KiK2i+1 小根堆(2)KiK2i 且 KiK2i+1 大根堆 则称该序列为一个堆。堆对应于完全二叉树的存储结构,(i=1,2,.,n/2),96 83 27 38 11 9,1 2 3 4 5 6,大根堆,数据结构-第十章 内部排序,31,堆排序基本思想,将初始文件R1.n建成一个大根堆；第1趟：将关键字最大的记录(堆顶)R1与无序区 的最后一个记录Rn交换；再将新的无序 区R1.n-1调整为堆；第2趟：将R1与Rn-1交换；再将新的无序区R1.n-2调整为堆；.第i趟：将R1与Rn-i+1交换；再将新的无序区 R1.n-i调整为堆；.直到执行完第(n-1)趟为止。,R1,数据结构-第十章 内部排序,32,堆排序需解决的两个问题,如何由一个无序序列建成一个堆？如何在输出堆顶元素之后，调整剩余元素，使之成为一个新的堆？1）调整堆的方法筛选,38,65,76,27,13,49,50,97,76,65,50,27,13,49,38,97,堆,堆,堆,堆,27,65,50,76,13,49,38,97,65,27,50,76,13,49,38,97,堆,数据结构-第十章 内部排序,33,2）将初始记录序列R1.n建成大根堆,依次把以i=n/2，n/2-1，n/2-2，.，1为根的子树调整为堆，则完成了整个建堆的过程。（49，38，13，50，76，65，27，97）,49,13,38,27,65,76,50,97,49,13,38,27,65,76,97,50,49,65,97,27,13,76,50,38,数据结构-第十章 内部排序,34,算法描述,void HeapSort(HeapType/HeapSort,typedef SqList HeapType;,void HeapAdjust(HeapType/HeapAdjust,0 1 2 3 n,rc s,j,。,。,m,数据结构-第十章 内部排序,35,算法分析最坏情况O(nlog2n)建初始堆时，比较次数4n反复调整堆时，比较次数2nlog2n 实验表明：平均性能接近于最坏性能O(nlog2n)辅助空间复杂度：O(1)不稳定排序对记录数较大的文件很有效,数据结构-第十章 内部排序,36,10.5 归并排序(合并排序),归并的概念 指将两个或两个以上的同序序列归并成一个序列的操作。10.5.1 两路归并排序算法思想第1趟：将待排序列R1.n看作n个长度为1的有序子序列，两两归并，得到n/2个长度为2的有序子序列(或最后一个子序列长度为1)；第2趟：将上述n/2个有序子序列两两归并；.直到合并成一个序列为止。,数据结构-第十章 内部排序,37,示例(n=7),(49)(38)(65)(97)(76)(49)(13)(38 49)(65 97)(49 76)(13)(38 49 65 97)(13 49 76)(13 38 49 49 65 76 97)性能分析任何情况时间复杂度O(nlog2n)空间复杂度O(n)很少用于内部排序,稳定排序,数据结构-第十章 内部排序,38,递归算法描述,Void MSort(RedType SR,RedType/将TR2s.m和TR2m+1.t 归并到TR1s.t/MSort,Void MergeSort(SqList&L)/将顺序表 L 进行归并排序 Msort(L.r,L.r,1,L.length)；/MergeSort,Void Merge(RedType SR,RedType/Merge,j,k,数据结构-第十章 内部排序,39,非递归算法描述,void MergeSort(SqList/MergeSort,数据结构-第十章 内部排序,40,10.5.2 自然两路归并排序,特点 以游程(自然的有序段)作为子序列进行归并，可以比直接两路归并更有效。示例 503 87 512 61 908 170 897 275 653 426 154 512 503 512 61 275 897 908 170 653 512 426 154 87 87 154 426 503 512 512 653 908 897 275 170 61 61 87 154 170 275 426 503 512 512 653 897 908,不稳定排序,数据结构-第十章 内部排序,41,10.6 基数排序(分配排序),特点 通过“分配”和“收集”过程来实现排序，时间复杂度可以突破基于关键字比较一类方法的下界O(nlgn)，达到O(n)。方法 借助多关键字排序的思想对单关键字排序多关键字排序示例 扑克牌排序(点数+花色)双关键字 花色：点数：23QKA“花色”地位高于“面值”最高位优先法（MSD法,Most Significant Digit first）按花色分成4堆；对每一堆：按面值分堆；从小到大排序；按花色从小到大排序,数据结构-第十章 内部排序,42,最低位优先法（LSD法,Least Significant Digit first）按点数大小分成13堆；按点数从小到大收集起来；再按花色分成四堆；按花色从小到大收集起来MSD与LSD不同特点按MSD排序，必须将序列逐层分割成若干子序列，然后对各子序列分别排序按LSD排序，不必分成子序列，对每个关键字都是整个序列参加排序；并且可不通过关键字比较，而通过若干次分配与收集实现排序,数据结构-第十章 内部排序,43,基数排序算法思想 借鉴LSD法 设参加排序的序列为K=K1,K2,.,Kn，其中Ki是d位rd进制的数，rd称为基数；d由所有元素中最长的一个元素的位数计量，Ki=Ki0 Ki1.Kid-1 从低位到高位依次对Kj(j=d-1,d-2,.,0)根据基数分配，再按基数递增序收集，则可得有序序列。例(1)K=3621 0724 8385 0075 0514 7368 0008 rd=10,d=4(2)K=Zhang Wang Li Zhao rd=27,d=5,高 低,数据结构-第十章 内部排序,44,链式基数排序示例 477 241 467 5 363 81 5,第1趟：分配 0 1 2 3 4 5 6 7 8 9 241 363 5 477 81 5 467 收集 241 81 363 5 5 477 467第2趟：分配 0 1 2 3 4 5 6 7 8 9 5 241 363 477 81 5 467 收集 5 5 241 363 467 477 81第3趟：分配 0 1 2 3 4 5 6 7 8 9 5 241 363 467 5 477 81 收集 5 5 81 241 363 467 477,rd=10 d=3,稳定排序,数据结构-第十章 内部排序,45,数据结构,主：静态链表r0.n数据域(key+otheritem)：记录指针域(next)：下一个记录的序号辅：f0.rd-1 各链式队列头指针 e0.rd-1 各链式队列尾指针数据结构定义,key otheritem next,012n,0rd-1,r0.n,f e,#define MAX_NUM_OF_KEY 8/可容纳的最多子关键字个数#define RADIX 10/关键字的基数rd#define MAX_SPACE 10000/记录空间可容纳的最多记录数typedef struct KeysType keyMAX_NUM_OF_KEY;InfoType otheritem;int next;SLCell;typedef struct SLCell rMAX_SPACE;/r0为头结点 int keynum;/实际划分的关键字位数d int recnum;/实际记录数SLList;Typedef int ArrTypeRADIX;,数据结构-第十章 内部排序,46,算法描述 主过程 RadixSort分配过程：Distribute收集过程：Collect,void RadixSort(SLList/RadixSort,数据结构-第十章 内部排序,47,void Distribute(SLCell/Distribute,void Collect(SLCell/Collect,数据结构-第十章 内部排序,48,链式基数排序的性能分析 设记录数为n，关键字位数为d,基数为rd每一趟：分配O(n)收集O(rd)d趟总计：O(d(n+rd)O(n)通常d,rd均为常数辅助空间n个指针域（游标）空间队头指针数组f0.rd-1和队尾指针数组e0.rd-1 辅助空间复杂度：O(rd+n),数据结构-第十章 内部排序,49,10.7 各种内部排序方法的比较,排序方法 最好时间 平均时间 最坏时间 辅助空间 稳定性直接插入 O(n)O(n2)O(n2)O(1)希尔 O(n1.3)O(1)冒泡 O(n)O(n2)O(n2)O(1)快速 O(nlog2n)O(nlog2n)O(n2)O(log2n)简单选择 O(n2)O(n2)O(n2)O(1)堆 O(nlog2n)O(nlog2n)O(nlog2n)O(1)归并 O(nlog2n)O(nlog2n)O(nlog2n)O(n)基数 O(d(rd+n)O(d(rd+n)O(d(rd+n)O(rd+n),数据结构-第十章 内部排序,50,按平均时间排序方法分为四类 O(n2)、O(nlgn)、O(n1+)、O(n)快速排序是目前基于比较的内部排序中最好的方法关键字随机分布时，快速排序的平均时间最短，堆排序次之，但后者所需的辅助空间少当n较小时如(n50)，可采用直接插入或简单选择排序，前者是稳定排序，但后者通常记录移动次数少于前者当n较大时，应采用时间复杂度为O(nlgn)的排序方法(主要为快速排序和堆排序)或者基数排序的方法，但后者对关键字的结构有一定要求当n较大时，为避免顺序存储时大量移动记录的时间开销，可考虑用链表作为存储结构（如插入排序、归并排序、基数排序）,数据结构-第十章 内部排序,51,快速排序和堆排序难于在链表上实现，可以采用地址排序的方法，之后再按辅助表的次序重排各记录文件初态基本按正序排列时，应选用直接插入、冒泡或随机的快速排序选择排序方法应综合考虑各种因素讨论：假设有 n 个值不同的元素存于顺序结构中，要求不经排序选出前k(kn)个最小元素，问哪些方法可用，哪些方法比较次数最少？,数据结构-第十章 内部排序,52,1.了解排序的定义和各种排序方法的特点。熟悉各种方法的排序过程及其依据的原则。基于“关键字间的比较”进行排序的方法可以按排序过程所依据的不同原则分为插入排序、交换排序、选择排序、归并排序和计数排序等五类。2.掌握各种排序方法的时间复杂度的分析方法。能从“关键字间的比较次数”分析排序算法的平均情况和最坏情况的时间性能。,本章学习要点,数据结构-第十章 内部排序,53,习题,1.以关键码序列(503,087,512,061,908,170,897,275,653,426)为例，手工执行以下排序算法，写出每一趟排序结束时的关键码状态：(1)直接插入排序(2)希尔排序(d1=5,d2=3,d3=1)(3)快速排序(4)堆排序（用小根堆）(5)归并排序(6)基数排序2.设有 n 个值不同的元素存于顺序结构中，问能否用比 2n-3 次少的比较次数找出该序列的最大值和最小值？若能，应如何实现？,数据结构-第十章 内部排序,54,上机作业,1.在双向链表上实现快速排序的递归算法。2.(选做)按下述原则编写快排的非递归算法：(1)一趟排序之后，若子序列已有序(无交换)，则不参加排序，否则先对长度较短的子序列进行排序，且将另一子序列的上、下界入栈保存；(2)若待排记录数3，则不再进行分割，而是直接进行比较排序之。测试实例：49 38 65 97 76 13 27 49 88 21 105,