数据结构-王红梅-第8章 排序技术.ppt

《数据结构-王红梅-第8章 排序技术.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第8章排序技术本章的基本内容是：排序的基本概念插入排序交换排序(起泡、快速)选择排序(简单选择、堆)归并排序分配排序各种排序算法的比较8.1概述排序：给定一组记录的集合{r1,r2,……,rn}，其相应的关键码分别为{k1,k2,……,kn}，排序是将这些记录排列成顺序为{rs1,rs2,……,rsn}的一个序列，使得相应的关键码满足ks1≤ks2≤……≤ksn（称为升序）或ks1≥ks2≥……≥ksn（称为降序）。正序：待排序序列中的记录已按关键码排好序。逆序（反序）：待排序序列中记录的排列顺序与排好序的顺序正好相反。排序的基本概念从操作

2、角度看，排序是线性结构的一种操作排序算法的稳定性：假定在待排序的记录集中，存在多个具有相同键值的记录，若经过排序，这些记录的相对次序仍然保持不变，即在原序列中，ki=kj且ri在rj之前，而在排序后的序列中，ri仍在rj之前，则称这种排序算法是稳定的；否则称为不稳定的。排序的基本概念学号姓名高数英语思想品德0001王军85880002李明64920003汤晓影8586………687278……8.1概述排序的基本概念单键排序：根据一个关键码进行的排序；多键排序：根据多个关键码进行的排序。学号姓名高数英语思想品德0001王军85880002李明6

3、4920003汤晓影8586………687278……按学号排序——单键排序按成绩（高数＋英语＋思想品德）排序——多键排序8.1概述排序的基本概念设关键码分别为k1,k2,…,km，多键排序有两种方法：⑴依次对记录进行m次排序，第一次按k1排序，第二次按k2排序，依此类推。这种方法要求各趟排序所用的算法是稳定的；⑵将关键码k1,k2,…,km分别视为字符串依次首尾连接在一起，形成一个新的字符串，然后，对记录序列按新形成的字符串排序。多键排序单键排序8.1概述排序的分类1.内排序：在排序的整个过程中，待排序的所有记录全部被放置在内存中2.外排序：

4、由于待排序的记录个数太多，不能同时放置在内存，而需要将一部分记录放置在内存，另一部分记录放置在外存上，整个排序过程需要在内外存之间多次交换数据才能得到排序的结果。排序的基本概念8.1概述排序的分类1.基于比较：基本操作——关键码的比较和记录的移动，其最差时间下限已经被证明为Ω（nlog2n）。（1）插入排序（2）交换排序（3）选择排序（4）归并排序2.不基于比较：根据关键码的分布特征。排序的基本概念8.1概述1.基本操作。内排序在排序过程中的基本操作：⑴比较：关键码之间的比较；⑵移动：记录从一个位置移动到另一个位置。2.辅助存储空间。辅助存

5、储空间是指在数据规模一定的条件下，除了存放待排序记录占用的存储空间之外，执行算法所需要的其他存储空间。3.算法本身的复杂程度。排序算法的性能8.1概述排序算法的存储结构从操作角度看，排序是线性结构的一种操作，待排序记录可以用顺序存储结构或链接存储结构存储。假定2：将待排序的记录序列排序为升序序列。intr[n+1];//待排序记录存储在r[1]~r[n]，r[0]留做他用假定1：采用顺序存储结构，关键码为整型，且记录只有关键码一个数据项。8.1概述8.2插入排序插入排序的主要操作是插入，其基本思想是：每次将一个待排序的记录按其关键码的大小插

6、入到一个已经排好序的有序序列中，直到全部记录排好序为止。基本思想：在插入第i（i＞1）个记录时，前面的i-1个记录已经排好序。直接插入排序有序序列无序序列r1r2ri-1rirnri+1…………r'1r'2r'i-1r'i……rnri+1……8.2插入排序基本思想：在插入第i（i＞1）个记录时，前面的i-1个记录已经排好序。（1）如何构造初始的有序序列？（2）如何查找待插入记录的插入位置?直接插入排序需解决的关键问题?8.2插入排序直接插入排序过程示例r0123456211825221025*212125i=218221025*25i=31

7、8221025*2225222110252115102525*2521151025*252118151018181025*i=418i=61825*i=5r[0]的作用?暂存单元监视哨8.2插入排序解决方法：将第1个记录看成是初始有序表，然后从第2个记录起依次插入到这个有序表中，直到将第n个记录插入。关键问题(1)如何构造初始的有序序列？算法描述：for(i=2;i<=n;i++){插入第i个记录，即第i趟直接插入排序；}8.2插入排序关键问题(2)如何查找待插入记录的插入位置?解决方法：在i-1个记录的有序区r[1]~r[i-1]中插入记

8、录r[i]，首先顺序查找r[i]的正确插入位置，然后将r[i]插入到相应位置。r[0]有两个作用：1.进入循环之前暂存了r[i]的值，使得不致于因记录的后移而丢失r[i]的内容；