北大数据结构与算法课件07内排序

数据结构与算法第七章内排序信息科学与技术学院网络与信息系统研究所北京大学信息学院张铭编写©版权所有，转载或翻印必究Page2大纲„7.1基本概念„7.2三种Ｏ(n2)的简单排序„7.3Shell排序„7.4基于分治法的排序„7.5堆排序„7.6分配排序和基数排序„7.7排序算法的理论和实验时间代价„7.8排序问题的下限北京大学信息学院张铭编写©版权所有，转载或翻印必究Page3排序问题„Google等搜索引擎返回结果排级„图书馆员书目编号、上架„各种排名„大学排名„考试成绩排名„《福布斯》富豪榜„Windows资源管理器，文件查看„„……北京大学信息学院张铭编写©版权所有，转载或翻印必究Page4小规模的排序问题„一个元素„已经有序了„两个元素„一次比较„若逆序？„一次交换=3次移动（赋值）„n个元素？453445北京大学信息学院张铭编写©版权所有，转载或翻印必究Page5排序算法的分类1„插入排序„直接插入排序、Shell排序„交换排序„冒泡排序、快速排序„选择排序„直接选择排序、堆排序„归并排序„分配排序„自底向上：低位优先LSD„自顶向下：高位优先MSD„地址排序北京大学信息学院张铭编写©版权所有，转载或翻印必究Page6排序算法的分类2„自底向上求解„三种Ｏ(n2)的简单排序„插入排序、冒泡排序、选择排序„Shell排序„堆排序„自顶向下求解：基于分治法的排序„归并排序、快速排序„分配排序„自底向上：低位优先LSD„自顶向下：高位优先MSD北京大学信息学院张铭编写©版权所有，转载或翻印必究Page77.1.1基本概念„记录(Record)：结点，进行排序的基本单位„关键码(Key)：唯一确定记录的一个或多个域„排序码(SortKey)：作为排序运算依据的一个或多个域„序列(Sequence)：线性表„由记录组成北京大学信息学院张铭编写©版权所有，转载或翻印必究Page8什么是排序？„排序„将序列中的记录按照排序码顺序排列起来„排序码域的值具有不减(或不增)的顺序„内排序„整个排序过程在内存中完成北京大学信息学院张铭编写©版权所有，转载或翻印必究Page9排序问题„给定一个序列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，称为不增序北京大学信息学院张铭编写©版权所有，转载或翻印必究Page10正序vs.逆序„“正序”序列：待排序序列正好符合排序要求„“逆序”序列：把待排序序列逆转过来，正好符合排序要求„例如，要求不升序列„08123496„96341208逆序！正序！北京大学信息学院张铭编写©版权所有，转载或翻印必究Page11排序的稳定性„稳定性„存在多个具有相同排序码的记录„排序后这些记录的相对次序保持不变„例如，341234’0896„08123434’96——稳定！„081234’3496——不稳定！北京大学信息学院张铭编写©版权所有，转载或翻印必究Page12排序算法的衡量标准„时间代价：记录的比较和移动次数„空间代价„算法本身的繁杂程度北京大学信息学院张铭编写©版权所有，转载或翻印必究Page137.1.3常用类和函数„总的排序类„Compare类„Swap函数„PrintArray函数北京大学信息学院张铭编写©版权所有，转载或翻印必究Page14总的排序类templateclassRecord,classCompareclassSorter{//总排序类protected://交换数组中的两个元素staticvoidswap(RecordArray[],inti,intj);public://对数组Array进行排序voidSort(RecordArray[],intn);//输出数组内容voidPrintArray(Recordarray[],intn);};北京大学信息学院张铭编写©版权所有，转载或翻印必究Page15Compare类„Compare类是用来比较记录的排序码„模板参数，方便针对不同类型的排序码进行比较„为了简便起见，本教材讨论整数排序的例子北京大学信息学院张铭编写©版权所有，转载或翻印必究Page16int_intCompare类classint_intCompare{//比较两个整型记录大小public:staticboollt(intx,inty){returnxy;}staticbooleq(intx,inty){returnx==y;}staticboolgt(intx,inty){returnxy;}staticboolle(intx,inty){returnx=y;}staticboolge(intx,inty){returnx=y;}};北京大学信息学院张铭编写©版权所有，转载或翻印必究Page17swap函数templateclassRecord,classComparevoidSorterRecord,Compare::swap(RecordArray[],inti,intj){//交换数组中的两个元素RecordTempRecord=Array[i];Array[i]=Array[j];Array[j]=TempRecord;}北京大学信息学院张铭编写©版权所有，转载或翻印必究Page18PrintArray函数templateclassRecord,classComparevoidSorterRecord,Compare::PrintArray(RecordArray[],intn){//输出数组内容for(inti=0;in;i++)coutArray[i];coutendl;}北京大学信息学院张铭编写©版权所有，转载或翻印必究Page197.2三种Ｏ(n2)的简单排序„插入排序(InsertSort)„冒泡排序(BubbleSort)„选择排序(SelectionSort)北京大学信息学院张铭编写©版权所有，转载或翻印必究Page207.2.1插入排序„算法思想„算法演示„直接插入排序„优化的插入排序„带监视哨的插入排序„二分法插入排序北京大学信息学院张铭编写©版权所有，转载或翻印必究Page2145‖34781234322964i=13445‖781234322964i=2344578‖1234322964i=312344578‖34322964i=41234344578‖322964i=5123234344578‖2964i=612293234344578‖64i=71229323434456478‖北京大学信息学院张铭编写©版权所有，转载或翻印必究Page22templateclassRecord,classComparevoidStraightInsertSorterRecord,Compare::Sort(RecordArray[],intn){//Array[]为待排序数组，n为数组长度for(inti=1;in;i++)//依次插入第i个记录{//依次与前面的记录进行比较，发现逆置就交换for(intj=i;j0;j--){if(Compare::lt(Array[j],Array[j-1]))swap(Array,j,j-1);elsebreak;//此时i前面记录已排序}}}北京大学信息学院张铭编写©版权所有，转载或翻印必究Page23算法分析„稳定„空间代价：Θ(1)„时间代价：„最佳情况：n-1次比较，0次交换，Θ(n)„最差情况：比较和交换次数为„平均情况：Θ(n2)121(1)/2()niinnn−==−=Θ∑北京大学信息学院张铭编写©版权所有，转载或翻印必究Page24优化的插入排序算法templateclassRecord,classCompareclassImprovedInsertSorter:publicInsertSorterRecord,Compare{//优化的插入排序类public:voidSort(RecordArray[],intn);};北京大学信息学院张铭编写©版权所有，转载或翻印必究Page25templateclassRecord,classComparevoidImprovedInsertSorterRecord,Compare::Sort(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;}}北京大学信息学院张铭编写©版权所有，转载或翻印必究Page26二分法插入排序„算法思想：„在插入第i个记录时，前面的记录已经是有序的了„可以用二分法查找第i个记录的正确位置北京大学信息学院张铭编写©版权所有，转载或翻印必究Page27算法分析„稳定„空间代价：Θ(1)„时间代价：„插入每个记录需要Θ(logi)次比较„最多移动i+1次，最少2次（移动临时记录）„因此最佳情况下总时间代价为Θ(nlogn)，最差和平均情况下仍为Θ(n2)北京大学信息学院张铭编写©版权所有，转载或翻印必究Page287.2.2冒泡排序„算法思想：„不停地比较相邻的记录，如果不满足排序要求，就交换相邻记录，直到所有的记录都已经排好序。北京大学信息学院张铭编写©版权所有，转载或翻印必究Page294534781234322964i=11245347829343264i=21229453478323464i=31229324534783464i=41229323445347864i=51229323434456478i=61229323434456478i=71229323434456478北京大学信息学院张铭编写©版权所有，转载或翻印必究Page30冒泡排序类templateclassRecord,classCompareclassBubbleSorter:publicSorterRecord,Compare{//冒泡排序类public:voidSort(RecordArray[],intn);};北京大学信息学院张铭编写©版权所有，转载或翻印必究Page31冒泡排序算法templateclassRecord,classComparevoidBubbleSorterRecord,Compare::Sort(RecordArray[],intn){//冒泡排序，Array[]为待排数组，n为数组长度//第i个记录冒泡for(inti=1;in;i++)//依次比较相邻记录，如果发现逆置，就交换for(intj=n-1;j=i;j--)if(Compare::lt(Array[j],Array[j-1]))swap(Array,j,j-1);}北京大学信息学院张铭编写©版权所有，转载或翻印必究Page32算法分析„稳定„空间代价：Θ(1)„时间代价：„比较次数：„交换次数最多为Θ(n2)，最少为0，平均为Θ(n2)。„最大，最小，平均时间代价均为Θ(n2)。121()(1)/2()nininnn−=−=−=Θ∑北京大学信息学院张铭编写©版权所有，转载或翻印必究Page33优化的冒泡排序„改进：检查每次冒泡过程中是否发生过交换，如果没有，则表明整个数组已经排好序了，排