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