8-数据结构与算法-北京大学2008-张铭-内排序

数据结构与算法第8章内排序本章由张铭主写://张铭，王腾蛟，赵海燕高等教育出版社，2008.6。“十一五”国家级规划教材“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。大纲8.1排序问题的基本概念8.2插入排序（Shell排序）8.3选择排序（堆排序）8.3交换排序8.4.1冒泡排序8.4.2快速排序8.5归并排序8.6分配排序和索引排序8.7排序算法的时间代价8.8内排序知识点总结“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。8.1基本概念记录(Record)：结点，进行排序的基本单位关键码(Key)：唯一确定记录的一个或多个域排序码(SortKey)：作为排序运算依据的一个或多个域序列(Sequence)：线性表由记录组成“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。什么是排序？排序将序列中的记录按照排序码顺序排列起来排序码域的值具有不减(或不增)的顺序内排序整个排序过程在内存中完成“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。排序问题给定一个序列R={r1,r2,…，rn}其排序码分别为k={k1,k2,…，kn}排序的目的：将记录按排序码重排形成新的有序序列R’={r’1,r’2,…，r’n}相应排序码为k’={k’1,k’2,…，k’n}排序码的顺序其中k’1≤k’2≤…≤k’n，称为不减序或k’1≥k’2≥…≥k’n，称为不增序“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。正序vs.逆序“正序”序列：待排序序列正好符合排序要求“逆序”序列：把待排序序列逆转过来，正好符合排序要求例如，要求不升序列0812349696341208逆序！正序！“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。排序的稳定性稳定性存在多个具有相同排序码的记录排序后这些记录的相对次序保持不变例如，341234’089608123434’96稳定！“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。排序的稳定性稳定性存在多个具有相同排序码的记录排序后这些记录的相对次序保持不变例如，341234’0896081234’3496不稳定！“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。稳定的形式化证明不稳定，反例说明341234’0896081234’3496“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。排序算法的衡量标准时间代价：记录的比较和移动次数空间代价算法本身的繁杂程度“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。8.2插入排序8.2.1直接插入排序8.2.2Shell排序“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。插入排序动画1234’322964453478“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。插入排序算法templateclassRecordvoidImprovedInsertSort(RecordArray[],intn){//Array[]为待排序数组，n为数组长度RecordTempRecord;//临时变量for(inti=1;in;i++){//依次插入第i个记录TempRecord=Array[i];//从i开始往前寻找记录i的正确位置intj=i-1;//将那些大于等于记录i的记录后移while((j=0)&&(Compare::lt(TempRecord,Array[j]))){Array[j+1]=Array[j];j=j-1;}//此时j后面就是记录i的正确位置，回填Array[j+1]=TempRecord;}}next“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。算法分析稳定空间代价：Θ(1)时间代价：最佳情况：n-1次比较，2(n-1)次移动，Θ(n)最差情况：比较和交换次数为平均情况：Θ(n2)121(1)/2()niinnn“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。8.2.2Shell排序直接插入排序的两个性质：在最好情况（序列本身已是有序的）下时间代价为Θ(n)对于短序列，直接插入排序比较有效Shell排序有效地利用了直接插入排序的这两个性质“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。Shell排序算法思想先将序列转化为若干小序列，在这些小序列内进行插入排序逐渐扩大小序列的规模，而减少小序列个数，使得待排序序列逐渐处于更有序的状态最后对整个序列进行扫尾直接插入排序，从而完成排序“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。shell排序动画1234’322964453478next“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。“增量每次除以2递减”的Shell排序templateclassRecordvoidShellSort(RecordArray[],intn){//Shell排序，Array[]为待排序数组，n为数组长度inti,delta;for(delta=n/2;delta0;delta/=2)//增量delta每次除以2递减for(i=0;idelta;i++)//分别对delta个子序列进行插入排序ModInsSort(&Array[i],n-i,delta);//“&”传Array[i]的地址，待处理数组长度为n-i//如果增量序列不能保证最后一个delta间距为1，可以安排下面这个扫尾性质的插入排序//ModInsSort(Array,n,1);}“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。针对增量而修改的插入排序算法templateclassRecordvoidModInsSort(RecordArray[],intn,intdelta){//修改的插入排序算法，参数delta表示当前的增量inti,j;for(i=delta;in;i+=delta)//对子序列中第i个记录，寻找合适的插入位置for(j=i;j=delta;j-=delta){//j以dealta为步长向前寻找逆置对进行调整if(Array[j]Array[j-delta])//逆置对swap(Array,j,j-delta);//交换Array[j]和Array[j-delta]elsebreak;}}“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。算法分析不稳定空间代价：Θ(1)增量每次除以2递减，时间代价：Θ(n2)选择适当的增量序列，可以使得时间代价接近Θ(n)“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。Shell排序选择增量序列增量每次除以2递减”时，效率仍然为Θ(n2)问题：选取的增量之间并不互质间距为2k-1的子序列都是由那些间距为2k的子序列组成的上一轮循环中这些子序列都已经排过序了，导致处理效率不高“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。Hibbard增量序列{2k-1，2k-1-1，…，7，3，1}，Shell(3)和Hibbard增量序列的Shell排序的效率可以达到Θ(n3/2)选取其他增量序列还可以更进一步减少时间代价“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。8.3选择排序8.3.1直接选择排序选出剩下的未排序记录中的最小记录，然后直接与数组中第i个记录交换，比冒泡排序减少了移动次数8.3.2堆排序堆排序：基于最大值堆来实现“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。直接选择排序动画1234’322964453478next“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。直接选择排序templateclassRecordvoidSelectSort(RecordArray[],intn){//依次选出第i小的记录，即剩余记录中最小的那个for(inti=0;in-1;i++){//首先假设记录i就是最小的intSmallest=i;//开始向后扫描所有剩余记录for(intj=i+1;jn;j++)//如果发现更小的记录，记录它的位置if(Compare::lt(Array[j],Array[Smallest]))Smallest=j;//将第i小的记录放在数组中第i个位置swap(Array,i,Smallest);}}“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。直接选择排序性能分析不稳定空间代价：Θ(1)时间代价：比较次数：Θ(n2)，与冒泡排序一样交换次数：n-1总时间代价：Θ(n2)“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。8.3.2堆排序选择类内排序直接选择排序：直接从剩余记录中线性查找最大记录堆排序：基于最大值堆来实现，效率更高选择类外排序置换选择排序赢者树、败方树“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。最大值堆排序过程示意图78344534’122932“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。最大值堆排序过程示意图32344534’122978“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。最大值堆排序过程示意图453434’32122978“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。最大值堆排序过程示意图343234’45122978“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。堆排序算法templateclassRecordvoidsort(RecordArray[],intn){inti;MaxHeapRecordmax_heap=MaxHeapRecord(Array,n,n);//建堆for(i=0;in-1;i++)//依次找出剩余记录中的最大记录，即堆顶max_heap.RemoveMax();//算法操作n-1次，最小元素不需要出堆}“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。算法分析建堆：Θ(n)删除堆顶:Θ(logi)一次建堆，n次删除堆顶总时间代价为Θ(nlogn)空间代价为Θ(1)“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。8.4交换排序8.4.1冒泡排序8.4.2快速排序“十一五”