数据结构与算法分析.ppt

第7章 排序 7.1 概述 7.2 插入排序 7.3 交换排序 7.4 选择排序 7.5 归并排序 7.6 外部排序 7.7 各种内排序方法的比较和 选择 7.1 概述 7.1.1 排序的基本概念 所谓排序就是整理文件中记录，使之按关键字递增（或递减）次序排列起来 其确切的定义如下： 假设含n个记录的序列为{R1，R2，．．．．．．Rn},其相应的关键字序列为{K1，K2，．．．．．．Kn} 需确定1，2，…，n的一种排列Ri1，Ri2，．．．．．．Rin，使其相应的关键字满足Ki1≤Ki2≤．．．．．．≤Kin（或Ki1≥Ki2≥．．．．．．≥Kin）的关系 7.1 概述 排序的对象 ：排序的对象是文件,它由一组记录组成。每条记录则由一个或若干个数据项(或域)组成 排序运算的依据：所谓关键字项就是可用来标识一个记录的一个或多个组合的数据项。该数据项的值称为关键字(Key)。需注意的是在不易产生混淆时，可将关键字项简称为关键字。用来作排序运算依据的关键字，可以是数字类型，也可以是字符类型。关键字的选取应根据问题的要求而定。 7.1 概述 7.1.2 排序的稳定性 当待排序记录的关键字均不相同时，排序结果是惟一的，否则排序结果不惟一。 在待排序的文件中，若存在多个关键字相同的记录，经过排序后这些具有相同关键字的记录之间的相对次序保持不变，该排序方法是稳定的；若具有相同关键字的记录之间的相对次序发生变化，则称这种排序方法是不稳定的。排序算法的稳定性是针对所有输入实例而言的。即在所有可能的输入实例中，只要有一个实例使得算法不满足稳定性要求，则该排序算法就是不稳定的。 7.1 概述 7.1.3 排序的分类 按在排序过程中是否涉及数据的内、外存交换来分类,排序大致分为两类,内部排序和外部排序。 对于外排序,可以进一步的分为两种方法: 合并排序法 直接合并排序法 对于内排序,按策略进行划分,可以分为: 插入排序 选择排序 交换排序 归并排序 分配排序 7.1 概述 7.1.4 排序算法分析 分析排序算法时，传统方法是衡量关键字之间进行比较的次数 排序算法分析应该考虑比较的次数和数据移动的次数 并不总是需要或是可能确定比较的准确次数，因此只能计算一个近似值 可以根据实际条件选择使用哪一种算法 7.2 插入排序 7.2.1 直接插入排序 1.基本思想 2.插入算法 3.Java程序 4.直接插入排序法的算法分析 (1)．算法的时间性能分析 (2)．算法的空间复杂度分析 (3)．直接插入排序的稳定性 7.2 插入排序 7.2.2 希尔排序 1.基本思想 2.具体算法 3.希尔排序的算法分析 (1)．增量序列的选择 (2)．Shell排序的时间性能优于直接插入排序 7.2 插入排序 希尔排序的时间性能优于直接插入排序的原因： ①当文件初态基本有序时直接插入排序所需的比较和移动次数均较少。 ②当n值较小时，n和n2的差别也较小，即直接插入排序的最好时间复杂度O(n)和最坏时间复杂度0(n2)差别不大。 ③在希尔排序开始时增量较大，分组较多，每组的记录数目少，故各组内直接插入较快，后来增量di逐渐缩小，分组数逐渐减少，而各组的记录数目逐渐增多，但由于已经按di-1作为距离排过序，使文件较接近于有序状态，所以新的一趟排序过程也较快。 因此，希尔排序在效率上较直接插人排序有较大的改进。 (3)．稳定性 希尔排序是一种不稳定排序方法。 7.3 交换排序 7.3.1 冒泡排序 1.基本思想 2. 具体算法 3.Java程序 4.冒泡排序的算法分析 （1）算法的最好时间复杂度 （2）算法的最坏时间复杂度 （3）算法的平均时间复杂度为O(n2) （4）算法稳定性 7.3 交换排序 5.冒泡排序的算法改进 (1)记住最后一次交换发生位置lastExchange的冒泡排序 (2) 改变扫描方向的冒泡排序 ①冒泡排序的不对称性 ②造成不对称性的原因 ③改进不对称性的方法 7.3 交换排序 7.3.2 快速排序 1.基本思想 2.具体算法 3.算法分析 （1）最坏时间复杂度 （2）最好时间复杂度 （3）基准关键字的选取 ①“三者取中”的规则 ② 取位于low和high之间的随机数 k(low≤k≤high)，用R[k]作为基准 （4）平均时间复杂度 （5）空间复杂度