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