排 序排序是数据处理中经常使用的一种重要运算研究问题:p如何进行排序p如何进行高效率排序1排序的基本概念 假设条件: 假定排序的对象是由一组记录组成的文 件，记录由若干字段组成，以排序码为 依据排序 排序码-记录中的一个(或多个)字段 关键码-此时按关键码排序、排序的结果唯 一 不是关键码-则可能有多个记录具有相同的 排序码，排序的结果不唯一2 排序:设R0,R1,Rn-1是由n个记录组 成的文件，K0,K1,Kn-1是排序码集 合，排序是将记录按排序码不增(或不 减)的次序排列 排序的稳定与不稳定基本概念3 按排序方法: 插入排序 选择排序 交换排序 分配排序 归并排序 按排序中涉及的存储器不同: 内排序:待排序的记录在排序过程中全部存放在 内存的 外排序:如果排序过程中需要使用外存的排序的种类4排序的基本操作 比较 比较两个关键字的大小 必须操作 移动 将一个记录从一个位置移动到另一个位置 非必须操作,可通过存储方式来避免(如静态链 表)5 评价排序算法好坏的标准 执行算法所需的时间 执行算法所需要的附加空间 算法本身的复杂程度也是考虑的一个因素 排序的时间开销是算法好坏的最重要的 标志 排序的时间开销衡量标准: 算法执行中的比较次数 算法执行中的移动次数 排序算法的评价6插入排序 基本方法每步将一个待排序的记录，按其排序码 大小插到前面已经排序的文件中的适当 位置，直到全部插入完为止。 种类： n直接插入排序 n二分法插入排序 n表插入排序 nshell排序7直接插入排序 方法: 假设待排序的n个记录R0,R1,Rn-1存放 在数组中，插入记录Ri时，记录集合被划 分为两个区间R0，Ri-1 和Ri，Rn-1 R0，Ri-1 已经排好序 Ri，Rn-1 是当前未排序的部分 将排序码Ki与Ki-1，Ki-2，K0依次比较， 找出应该插入的位置，将记录Ri插入，原 位置的记录向后顺移 直接插入排序采用顺序存储结构 8直接插入排序的算法初始化 申明temp为记录结点类型j=i-1将关键码比temp大的记录后移 recordj+1=recordj继续向前比较 j-endi0 Yj != i-1？NY找到插入位置将temp插入 recordj+1=tempAA下标为i的记录位置不变N9二分法插入排序 直接插入排序的算法简洁，容易实现，n 较小时 是一种很好的排序方法 通常文件中记录的数量都很大，则此时直接插 入排序方法不适用 在直接插入排序的基础上减少比较的次数，即 在插入Ri时改用二分法比较找插入位置，便得到 二分法插入排序 10 二分法插入排序必须采用顺序存储方式二分法插入排序的算法初始化 申明temp为记录结点类型i记录长度？temp=下标为i的记录left=right?left=0,right=i-1mid=(left+right)/2Temp的关键码以mid 为下标的记录关键码right=mid-1endNYYNY left=mid+1ANBB将记录按找到的位置向后移动C11二分法插入排序的算法(续)left != i？找到插入位置将temp插入 recordleft=tempY下标为i的记录位置不变ANC12选择排序 基本方法是每步从待排序记录中选出排序码最小的记录， 顺序放在已排序的记录序列的后面，直到全部 排完。 直接选择排序 堆排序13直接选择排序 方法是 首先在所有记录中选出排序码最小的记录， 与第一个记录交换 然后在其余的记录中再选出排序码最小的记 录与第二个记录交换 以此类推，直到所有记录排好序14 初始序列为 49,38,65,97,49,13,27,76(1)49 38 65 97 49 13 27 76 (2)1338 65 97 49 49 27 76 (3)13 2765 97 49 49 38 76 (4)13 27 3897 49 49 65 76 (5) 举 例15交换排序 基本方法： 两两比较待排序记录的排序码，交 换不满足顺序要求的偶对，直到全 部满足为止 种类： 起泡排序方法 快速排序方法16起泡排序方法 通过相邻记录之间的比较与交换，使值较小( 大)的记录逐步从后向前移，就像水底的气泡 一样向上冒，故称为起泡排序 基本思想 Ri与Ri+1比较，若前者大于后者，则两个记 录交换位置，否则不交换 从(R0，R1)到(Rn-2，Rn-1)的n-1次比较和交 换过程称为一次起泡。经过这次起泡，n个 记录中最大者被安置在第n个位置上 再对前n-1个记录进行同样处理 ，这样 最多做n-1次起泡就能完成排序。 17 改进：可以设置一个标志noswap表示本次起泡是 否有记录交换，如果没有交换则表示整个 排序过程完成起泡排序方法18初始序列: 49 38 65 97 76 13 27 49 第一趟起泡 38 49657613274997 第二趟起泡 38 49651327497697 第三趟起泡 38 49132749657697 例 题19快速排序方法 快速排序是对起泡排序的改进 起泡排序在相邻两个记录间比较和交换，每 次交换只能上移或下移一个位置，导致总的 比较与移动次数增多 快速排序又称分区交换排序，是由C.A.R Hoar提出的 快速排序方法记录间比较次数较少，因而速 度较快，被认为是较好的排序方法20 设待排序的n个记录R0, R1, Rn-1存放在数组R中， 选取第一个记录R0为标准 一趟快速排序快速排序是寻找记录R0的最终位置，若 一趟排序完毕后，数组分为两个部分 R0,Ri-1 存放的为小于R0的记录 Ri+1,Rn-1 存放的为大于R0的记录 i为R0的最终位置 把当前参加排序的记录按Key分成前后两个部分的过 程称为对两个子序列分别重复上述过程，直到所有记 录都排好序快速排序基本思想21 设置变量i指向参加排序的序列中第一个位置0， 变量j指向参加排序的序列中最后位置n-1 首先保存记录R0， R0为空出的位置，空位在前一区; 令j向前扫描，寻找小于R0的记录，找到小于R0的记 录Rj，将记录Rj移到当前空位中,Rj为空位在后一 区; 令i向后扫描，寻找大于R0的记录，找到大于R0的记 录Ri，将记录Ri移到当前空位中，空位到了前一区 ; 再令j自j-1起向前扫描 如此交替改变扫描方向，从两端向中间靠拢， 直到i=j，这时i所指的位置为R0的最终位置快速排序实现策略22初始序列为49, 38, 65, 97, 76, 13, 27, 49例 题(1)一次分区过程如下 j向左扫描 49 38659776132749ij i向右扫描 27 3865977613 49 ij J向左扫描 27 38 97 7613 6549i j 23例 题(续)i向右扫描 27 38 13 97 76 6549i j j向左扫描，位置不变 27 38 13 76 97 6549i j i=j,找到R0的最终位置 27 38 13 49 76 976549ij 递归处理R0的左/右区间24分配排序是一种借助多关键码排序思 想对单逻辑关键码排序的方法分配排序*25 例子扑克牌排序 要求:每张扑克牌具有两个属性花色(梅花 方块红心黑桃)和面值 (2310JQKA)，且花色的地位 高于面值，排序后为梅花2，梅花A ，方块2，方块A，红心2，红心 A，黑桃2，黑桃A分配排序算法26分配排序例 排序有以下两种方法第一是先将牌按花色分成4堆，然后将每堆按面值 从小到大排序，最后按花色从小到大迭在一起第二种是先将牌按面值大小分成13堆，然后从小 到大把它们收集起来，再按花色分成4堆，最后 顺序地收集起来27分配排序算法一般情况下，假设文件F有n个记录 F=(R0，R1，Rn-1) 且每个记录Ri中含有d个关键码(ki0, ki1, kid-1)， 则文件F对关键码(k0,k1,kd-1)有序是指 文件中任意两个记录Ri和Rj(0ijn-1)满足词典 次序有序关系 (ki0, ki1, kid-1) (kj0, kj1, kjd-1) 其中k0称为最高位关键码，kd-1称为最低位关键码28 实现多关键码排序，有两种方法 高位优先法: 先对最高位关键码k0排序，将文件分成若干堆每 堆中的记录都具有相同的k0 然后分别就每堆对关键码k1排序，分成若干子堆 ，如此重复，直到对kd-1排序 最后将各堆按次序叠在一起成为一个有序文件 低位优先法: 从最低位关键码kd-1起排序 然后再对高一位关键码kd-2排序 如此重复，直到对K0排序后便成为一个有序文件分配排序算法(续)29 低位优先法比高位优先法简单 高位优先排序必须将文件逐层分割成若干子 文件，然后各子文件独立排序 低位优先排序不必分成子堆，对每个关键码 都是整个文件参加排序，且可通过若干次“ 分配”和“收集”实现排序 基数排序就是用低位优先法对单逻辑关 键码排序的一种方法分配排序算法(续)30方法:把每个排序码看成是一个d元组 Ki=(Ki0, Ki1, Kid-1) 其中每个Ki都是集合C0，C1，Cr-1 (C0C1Cr-1)中的值 即C0KijCr-1(0in-1,0jd-1) 其中r称为基数 排序时先按Kid-1从小到大将记录分配到r个堆中 然后依次收集，再按Kid-2分配到r个堆中 如此反复，直到对Ki0分配、收集，得到的便是 排好序的序列基数排序31基数排序方法(续) 基数排序时，为了实现记录的分配和收集 ，可以设r个队列，排序前为空队列，分 配时将记录插入到各自的队列中，收集 时将队列中的记录排在一起32基数排序例(1)(1)初始状态初始状态36516989547323648103651698954732364810 (2)第一趟分配后(3)(3)第一趟收集后第一趟收集后10325953616364798481032595361636479848 33基数排序例(续)(4)第二趟分配后(5)第二趟收集后5101632363647489598 34归并排序的主要思想是 把待排序的文件分成若干个子文件，先将每 个子文件内的记录排序 再将已排序的子文件合并，得到完全排序的 文件 合并时只要比较各子文件第一个记录的排序码， 排序码最小的记录为排序后的第一个记录，取出 该记录 继续比较各子文件的第一个记录，记录，找出排 序后的第二个记录 如此反复，经过一次扫描，得到排序结果归并排序*35 设文件中有n个记录，可以看成n个子文件，每 个子文件中只包含1个记录先将每两个子文件归并，得到n/2个部分排序的 较大的子文件，每个子文件包含2个记录 再将子文件归并，如此反复，直到得到一个文 件 上述每步归并都是将两个子文件合成一个子文 件，称为“二路归并排序”。 类似地还有“三路归并排序”或“多路归并排序”二路归并排序36