数据结构与算法第七章内排序

《数据结构与算法第七章内排序》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、数据结构与算法第七章内排序任课教员：张铭http://db.pku.edu.cn/mzhang/DS/mzhang@db.pku.edu.cn北京大学信息科学与技术学院网络与信息系统研究所©版权所有，转载或翻印必究大纲¢7.1基本概念2¢7.2三种Ｏ(n)的简单排序¢7.3Shell排序¢7.4基于分治法的排序¢7.5堆排序¢7.6分配排序和基数排序¢7.7排序算法的理论和实验时间代价¢7.8排序问题的下限北京大学信息学院张铭编写©版权所有，转载或翻印必究Page2排序问题¢Google等搜索引擎返回结果排级¢图书馆员书目编号、上架¢各

2、种排名¢大学排名¢考试成绩排名¢《福布斯》富豪榜¢Windows资源管理器，文件查看¢www.kooxoo.com¢……北京大学信息学院张铭编写©版权所有，转载或翻印必究Page3小规模的排序问题¢一个元素45¢已经有序了¢两个元素4534¢一次比较¢若逆序？¢一次交换=3次移动（赋值）¢n个元素？北京大学信息学院张铭编写©版权所有，转载或翻印必究Page4排序算法的分类1¢插入排序¢直接插入排序、Shell排序¢交换排序¢冒泡排序、快速排序¢选择排序¢直接选择排序、堆排序¢归并排序¢分配排序¢自底向上：低位优先LSD¢自顶向下：高位优

3、先MSD¢地址排序北京大学信息学院张铭编写©版权所有，转载或翻印必究Page5排序算法的分类2¢自底向上求解2¢三种Ｏ(n)的简单排序¢插入排序、冒泡排序、选择排序¢Shell排序¢堆排序¢自顶向下求解：基于分治法的排序¢归并排序、快速排序¢分配排序¢自底向上：低位优先LSD¢自顶向下：高位优先MSD北京大学信息学院张铭编写©版权所有，转载或翻印必究Page67.1.1基本概念¢记录(Record)：结点，进行排序的基本单位¢关键码(Key)：唯一确定记录的一个或多个域¢排序码(SortKey)：作为排序运算依据的一个或多个域¢序列(S

4、equence)：线性表¢由记录组成北京大学信息学院张铭编写©版权所有，转载或翻印必究Page7什么是排序？¢排序¢将序列中的记录按照排序码顺序排列起来¢排序码域的值具有不减(或不增)的顺序¢内排序¢整个排序过程在内存中完成北京大学信息学院张铭编写©版权所有，转载或翻印必究Page8排序问题¢给定一个序列R={r1,r2,…，rn}¢其排序码分别为k={k1,k2,…，kn}¢排序的目的：将记录按排序码重排¢形成新的有序序列R’={r’1,r’2,…，r’n}¢相应排序码为k’={k’1,k’2,…，k’n}¢排序码的顺序¢其中k’1≤

5、k’2≤…≤k’n，称为不减序¢或k’1≥k’2≥…≥k’n，称为不增序北京大学信息学院张铭编写©版权所有，转载或翻印必究Page9正序vs.逆序¢“正序”序列：待排序序列正好符合排序要求¢“逆序”序列：把待排序序列逆转过来，正好符合排序要求¢例如，要求不升序列逆序！¢08123496¢96341208正序！北京大学信息学院张铭编写©版权所有，转载或翻印必究Page10排序的稳定性¢稳定性¢存在多个具有相同排序码的记录¢排序后这些记录的相对次序保持不变¢例如，341234’0896¢08123434’96——稳定！¢081234’349

6、6——不稳定！北京大学信息学院张铭编写©版权所有，转载或翻印必究Page11排序算法的衡量标准¢时间代价：记录的比较和移动次数¢空间代价¢算法本身的繁杂程度北京大学信息学院张铭编写©版权所有，转载或翻印必究Page127.1.3常用类和函数¢总的排序类¢Compare类¢Swap函数¢PrintArray函数北京大学信息学院张铭编写©版权所有，转载或翻印必究Page13总的排序类templateclassSorter{//总排序类protected://交换数组中的两个元素static

7、voidswap(RecordArray[],inti,intj);public://对数组Array进行排序voidSort(RecordArray[],intn);//输出数组内容voidPrintArray(Recordarray[],intn);};北京大学信息学院张铭编写©版权所有，转载或翻印必究Page14Compare类¢Compare类是用来比较记录的排序码¢模板参数，方便针对不同类型的排序码进行比较¢为了简便起见，本教材讨论整数排序的例子北京大学信息学院张铭编写©版权所有，转载或翻印必究Page15int_intCom

8、pare类classint_intCompare{//比较两个整型记录大小public:staticboollt(intx,inty){returnx