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

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

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

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

3、向下求解：基于分治法的排序¢归并排序¢归并排序、快速排序¢分配排序¢分配排序¢自底向上：低位优先LSD¢自顶向下：高位优先MSD¢自底向上：低位优先LSD¢地址排序¢自顶向下：高位优先MSD北京大学信息学院张铭编写©版权所有，转载或翻印必究Page5北京大学信息学院张铭编写©版权所有，转载或翻印必究Page617.1.1基本概念什么是排序？¢记录(Record)：结点，进行排序的基¢排序本单位¢将序列中的记录按照排序码顺序排列起来¢关键码(Key)：唯一确定记录的一个或多个域¢排序码域的值具有不减(或不增)的顺序¢排序码(SortKey)：作为排序运算依¢内排序

4、据的一个或多个域¢整个排序过程在内存中完成¢序列(Sequence)：线性表¢由记录组成北京大学信息学院张铭编写©版权所有，转载或翻印必究Page7北京大学信息学院张铭编写©版权所有，转载或翻印必究Page8排序问题正序vs.逆序¢给定一个序列R={r1,r2,…，rn}¢“正序”序列：待排序序列正好符合¢其排序码分别为k={k1,k2,…，kn}排序要求¢排序的目的：将记录按排序码重排¢“逆序”序列：把待排序序列逆转过¢形成新的有序序列R’={r’1,r’2,…，r’n}来，正好符合排序要求¢相应排序码为k’={k’1,k’2,…，k’n}¢例如，要求不升序列

5、逆序！¢排序码的顺序¢其中k’1≤k’2≤…≤k’n，称为不减序¢08123496¢或k’1≥k’2≥…≥k’n，称为不增序¢96341208正序！北京大学信息学院张铭编写©版权所有，转载或翻印必究Page9北京大学信息学院张铭编写©版权所有，转载或翻印必究Page10排序的稳定性排序算法的衡量标准¢稳定性¢时间代价：记录的比较和移动次数¢存在多个具有相同排序码的记录¢空间代价¢排序后这些记录的相对次序保持不变¢例如，341234’0896¢算法本身的繁杂程度¢08123434’96——稳定！¢081234’3496——不稳定！北京大学信息学院张铭编写©版权所有

6、，转载或翻印必究Page11北京大学信息学院张铭编写©版权所有，转载或翻印必究Page1227.1.3常用类和函数总的排序类templateclassSorter{//总排序类¢总的排序类protected://交换数组中的两个元素¢Compare类staticvoidswap(RecordArray[],inti,intj);¢Swap函数public:¢PrintArray函数//对数组Array进行排序voidSort(RecordArray[],intn);//输出数组内容voidPrintArray(

7、Recordarray[],intn);};北京大学信息学院张铭编写©版权所有，转载或翻印必究Page13北京大学信息学院张铭编写©版权所有，转载或翻印必究Page14Compare类int_intCompare类classint_intCompare{¢Compare类是用来比较记录的//比较两个整型记录大小排序码public:staticboollt(intx,inty){returnx

8、eturnx>y;}st