选修1《排序》ppt课件 高中信息技术.ppt

排序排序是数据处理中经常使用的一种重要运算研究问题 如何进行排序如何进行高效率排序 排序的基本概念 假设条件 假定排序的对象是由一组记录组成的文件 记录由若干字段组成 以排序码为依据排序排序码 记录中的一个 或多个 字段关键码 此时按关键码排序 排序的结果唯一不是关键码 则可能有多个记录具有相同的排序码 排序的结果不唯一 排序 设 R0 R1 Rn 1 是由n个记录组成的文件 K0 K1 Kn 1 是排序码集合 排序是将记录按排序码不增 或不减 的次序排列排序的稳定与不稳定 基本概念 按排序方法 插入排序选择排序交换排序分配排序归并排序按排序中涉及的存储器不同 内排序 待排序的记录在排序过程中全部存放在内存的外排序 如果排序过程中需要使用外存的 排序的种类 排序的基本操作 比较比较两个关键字的大小必须操作移动将一个记录从一个位置移动到另一个位置非必须操作 可通过存储方式来避免 如静态链表 评价排序算法好坏的标准执行算法所需的时间执行算法所需要的附加空间算法本身的复杂程度也是考虑的一个因素排序的时间开销是算法好坏的最重要的标志排序的时间开销衡量标准 算法执行中的比较次数算法执行中的移动次数 排序算法的评价 7 金手指考试网元贝驾考网科目一科目四仿真考试题C1 Grammar 插入排序 基本方法 每步将一个待排序的记录 按其排序码大小插到前面已经排序的文件中的适当位置 直到全部插入完为止 种类 直接插入排序二分法插入排序表插入排序shell排序 直接插入排序 方法 假设待排序的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插入 原位置的记录向后顺移直接插入排序采用顺序存储结构 直接插入排序的算法 二分法插入排序 直接插入排序的算法简洁 容易实现 n较小时是一种很好的排序方法通常文件中记录的数量都很大 则此时直接插入排序方法不适用在直接插入排序的基础上减少比较的次数 即在插入Ri时改用二分法比较找插入位置 便得到二分法插入排序 二分法插入排序必须采用顺序存储方式 二分法插入排序的算法 二分法插入排序的算法 续 left i 找到插入位置将temp插入record left temp Y 下标为i的记录位置不变 A N C 选择排序 基本方法是每步从待排序记录中选出排序码最小的记录 顺序放在已排序的记录序列的后面 直到全部排完 直接选择排序堆排序 直接选择排序 方法是首先在所有记录中选出排序码最小的记录 与第一个记录交换然后在其余的记录中再选出排序码最小的记录与第二个记录交换以此类推 直到所有记录排好序 初始序列为49 38 65 97 49 13 27 76 1 4938659749 132776 2 13 38659749 492776 3 1327 659749 493876 4 132738 9749 496576 5 举例 交换排序 基本方法 两两比较待排序记录的排序码 交换不满足顺序要求的偶对 直到全部满足为止种类 起泡排序方法快速排序方法 起泡排序方法 通过相邻记录之间的比较与交换 使值较小 大 的记录逐步从后向前移 就像水底的气泡一样向上冒 故称为起泡排序基本思想Ri与Ri 1比较 若前者大于后者 则两个记录交换位置 否则不交换从 R0 R1 到 Rn 2 Rn 1 的n 1次比较和交换过程称为一次起泡 经过这次起泡 n个记录中最大者被安置在第n个位置上再对前n 1个记录进行同样处理 这样最多做n 1次起泡就能完成排序 改进 可以设置一个标志noswap表示本次起泡是否有记录交换 如果没有交换则表示整个排序过程完成 起泡排序方法 初始序列 4938659776132749 第一趟起泡 38496576132749 97 第二趟起泡 384965132749 7697 第三趟起泡 3849132749 657697 例题 快速排序方法 快速排序是对起泡排序的改进起泡排序在相邻两个记录间比较和交换 每次交换只能上移或下移一个位置 导致总的比较与移动次数增多快速排序又称分区交换排序 是由C A RHoar提出的快速排序方法记录间比较次数较少 因而速度较快 被认为是较好的排序方法 设待排序的n个记录 R0 R1 Rn 1 存放在数组R中 选取第一个记录R0为标准一趟快速排序快速排序是寻找记录R0的最终位置 若一趟排序完毕后 数组 分为两个部分 R 0 R i 1 存放的为小于R0的记录 R i 1 R n 1 存放的为大于R0的记录 i 为R0的最终位置把当前参加排序的记录按Key 分成前后两个部分的过程称为对两个子序列分别重复上述过程 直到所有记录都排好序 快速排序基本思想 设置变量i指向参加排序的序列中第一个位置0 变量j指向参加排序的序列中最后位置n 1首先保存记录R0 R 0 为空出的位置 空位在前一区 令j向前扫描 寻找小于R0的记录 找到小于R0的记录R j 将记录R j 移到当前空位中 R j 为空位在后一区 令i向后扫描 寻找大于R0的记录 找到大于R0的记录R i 将记录R i 移到当前空位中 空位到了前一区 再令j自j 1起向前扫描 如此交替改变扫描方向 从两端向中间靠拢 直到i j 这时i所指的位置为R0的最终位置 快速排序实现策略 初始序列为49 38 65 97 76 13 27 49 例题 1 一次分区过程如下 j向左扫描 4938659776132749 i j i向右扫描 27386597761349 i j J向左扫描 27389776136549 i j 例题 续 i向右扫描 27381397766549 i j j向左扫描 位置不变 27381376976549 i j i j 找到R0的最终位置 2738134976976549 i j 递归处理R0的左 右区间 分配排序是一种借助多关键码排序思想对单逻辑关键码排序的方法 分配排序 例子 扑克牌排序要求 每张扑克牌具有两个属性 花色 梅花 方块 红心 黑桃 和面值 2 3 10 J Q K A 且花色的地位高于面值 排序后为 梅花2 梅花A 方块2 方块A 红心2 红心A 黑桃2 黑桃A 分配排序算法 分配排序例 排序有以下两种方法 第一是先将牌按花色分成4堆 然后将每堆按面值从小到大排序 最后按花色从小到大迭在一起第二种是先将牌按面值大小分成13堆 然后从小到大把它们收集起来 再按花色分成4堆 最后顺序地收集起来 分配排序算法 一般情况下 假设文件F有n个记录F R0 R1 Rn 1 且每个记录Ri中含有d个关键码 ki0 ki1 kid 1 则文件F对关键码 k0 k1 kd 1 有序是指 文件中任意两个记录Ri和Rj 0 i j n 1 满足词典次序有序关系 ki0 ki1 kid 1 kj0 kj1 kjd 1 其中k0称为最高位关键码 kd 1称为最低位关键码 实现多关键码排序 有两种方法 高位优先法 先对最高位关键码k0排序 将文件分成若干堆每堆中的记录都具有相同的k0然后分别就每堆对关键码k1排序 分成若干子堆 如此重复 直到对kd 1排序最后将各堆按次序叠在一起成为一个有序文件低位优先法 从最低位关键码kd 1起排序然后再对高一位关键码kd 2排序如此重复 直到对K0排序后便成为一个有序文件 分配排序算法 续 低位优先法比高位优先法简单高位优先排序必须将文件逐层分割成若干子文件 然后各子文件独立排序低位优先排序不必分成子堆 对每个关键码都是整个文件参加排序 且可通过若干次 分配 和 收集 实现排序基数排序就是用低位优先法对单逻辑关键码排序的一种方法 分配排序算法 续 方法 把每个排序码看成是一个d元组 Ki Ki0 Ki1 Kid 1 其中每个Ki都是集合 C0 C1 Cr 1 C0 C1 Cr 1 中的值即C0 Kij Cr 1 0 i n 1 0 j d 1 其中r称为基数排序时先按Kid 1从小到大将记录分配到r个堆中然后依次收集 再按Kid 2分配到r个堆中如此反复 直到对Ki0分配 收集 得到的便是排好序的序列 基数排序 基数排序方法 续 基数排序时 为了实现记录的分配和收集 可以设r个队列 排序前为空队列 分配时将记录插入到各自的队列中 收集时将队列中的记录排在一起 基数排序例 1 初始状态36 5 16 98 95 47 32 36 48 10 2 第一趟分配后 3 第一趟收集后10 32 5 95 36 16 36 47 98 48 基数排序例 续 4 第二趟分配后 5 第二趟收集后5 10 16 32 36 36 47 48 95 98 设文件中有n个记录 可以看成n个子文件 每个子文件中只包含1个记录先将每两个子文件归并 得到n 2个部分排序的较大的子文件