计算机软及应用八排序PPT课件.ppt

第8章排序 1 第8章排序 学习目的要求 掌握排序的概念和排序的种类 熟练掌握五类基本排序 插入排序 交换排序 选择排序 归并排序和基数排序的算法思想 算法实现和性能分析 2 8 1排序的基本概念 8 2插入排序 8 3选择排序 8 4交换排序 8 5归并排序 8 6基数排序 8 7几种排序方法的比较 第8章排序 3 8 1排序的基本概念 假设含有n个记录的序列为 R1 R2 Rn 其相应的关键字序列为 K1 K2 Kn 一种排列P1 P2 Pn 使其相应的关键字满足如下非递减关系 满足非递增关系时 将 号改为 号 Kp1 Kp2 Kpn 使n个记录的无序序列成为一个按关键字有序的序列 Rp1 Rp2 Rpn 这样一种操作过程称为排序 排序 将一个数据元素 或记录 的任意序列 重新排列成一个按关键字有序的序列 4 学生档案表 8 1排序的基本概念 5 8 1排序的基本概念 排序过程中依据的不同原则 内部排序方法可大致分为插入排序 交换排序 选择排序 归并排序和基数排序等五类 评价排序算法优劣的标准 一是算法执行时所需的时间二是执行算法时所需要的附加空间执行排序的时间复杂性是算法优劣的重要的标志 6 影响时间复杂性的主要因素又可以用算法执行中的比较次数和移动次数来衡量 在排序的过程中常需进行两种基本操作 比较两个关键字的大小 将记录从一个位置移动至另一个位置 8 1排序的基本概念 7 待排序的记录序列存储方式 存放在地址连续的一组存储单元上 类似于线性表 排序时必须移动记录 存放在静态链表中 记录之间的次序关系由指针指定 排序时不需要移动记录 仅需修改指针 记录本身存储在一组地址连续的存储单元内 另设一个指示各个记录存储位置的地址向量 排序时仅需移动地址向量排序后再按照地址向量中的值调整记录的存储位置 8 1排序的基本概念 8 8 1排序的基本概念 若在排序期间具有相同键值的记录的相对位置不变 则称此排序方法是稳定的 否则称为不稳定的 9 8 2插入排序 插入排序 InsertionSort 的基本思想 每次将一个待排序的记录 按其关键字的大小插入到前面已经排好序的有序序列中的适当位置上 直到全部记录插入完成为止 直接插入排序折半插入排序2 路插入排序希尔排序 10 8 2 1直接插入排序 直接插入排序 StraightInsertionSort 是一种最简单的排序方法 基本操作 依次将记录序列中的每一个记录插入到有序序列中 使有序序列的长度不断地扩大 8 2插入排序 11 有序序列R 1 i 1 R i 无序序列R i n 一趟直接插入排序的基本思想 有序序列R 1 i 无序序列R i 1 n 12 一共需要经过n 1趟就可以将初始序列的n个记录重新排列成按关键字值大小排列的有序序列 过程如下 先将待排序记录序列中的第一个记录作为一个有序序列 将记录序列中的第二个记录插入到上述有序序列中形成由两个记录组成的有序序列 再将记录序列中的第三个记录插入到这个有序序列中 形成由三个记录组成的有序序列 如此进行下去 直到最后一个记录也插入完成 8 2插入排序 13 初始关键字 49 38659776132749 i 2 38 3849 659776132749 i 3 65 384965 9776132749 i 4 97 38496597 76132749 i 5 76 3849657697 132749 i 6 13 133849657697 2749 i 7 27 13273849657697 49 i 8 49 1327384949 657697 监视哨L r 0 直接插入排序是稳定的 14 注意 第二条记录和第八条记录的相对位置在排序后没有发生变化 此排序算法是稳定的 15 8 2插入排序 直接插入排序算法简单 易实现 其算法的时间复杂度是O n2 从空间复杂度来看 只需要一个记录大小的辅助空间用于暂存待插入的记录 当待排序记录较少时 排序速度较快 反之 当待排序的记录数量较大时 大量的比较和移动操作将使直接插入排序算法的效率降低 另外 若当待排序的数据元素基本有序时 排序过程中的记录移动次数会大大减少 从而效率会有所提高 直接插入排序是一种稳定的排序方法 16 8 2 2折半插入排序 折半插入排序是对直接插入排序的改进算法 它是利用折半查找来实现插入位置的定位 可减少排序过程中的比较次数 适用于待排序的记录数量较大的情况 8 2插入排序 17 一趟折半插入排序的步骤为 1 初始化将待插入的记录存入r 0 中 r 0 r i 给指定查找区间上下界指针赋值 low 1 high i 1 2 折半查找插入位置 3 将插入位置后面的记录依次后移一个位置 4 将暂存在r 0 中的待插入记录放入找到的位置上 8 2插入排序 18 1436495280 5861239775 i low high m m low low m high 14364952586180 239775 i low high m high m high m low 例如 再如 插入位置 插入位置 L r L r 19 折半插入排序只减少关键字间的比较次数 而记录的移动次数不变 故折半插入排序的时间复杂度仍为O n2 从空间复杂度来看 折半插入排序只需要一个记录大小的辅助空间用于暂存待插入的记录 这与直接插入排序相同 折半插入排序是一种稳定的排序方法 8 2插入排序 20 8 2 32 路插入排序 2 路插入排序是对折半插入排序的改进算法 它是利用增加辅助空间来减少排序过程中移动记录的次数 即 以空间换时间 8 2插入排序 21 具体做法是 建立一个和待排序序列r n 同类型的数组d n 作为辅助空间 先将r 0 的值赋给d 0 将d 0 看成是处于最后有序序列中处于中间位置的记录 再从r 1 开始依次将记录插入到d 0 之前或之后的有序序列中 将数组d看成是一循环向量 既首尾相连的环状空间 并设置两个指针first和final分别指向有序序列的第一条和最后一条记录 将当前待插入记录r i 与d 0 比较 若r i d 0 则将其插入d 0 之前的有序序列中 反之 则将其插入到d 0 之后的有序序列中 当所有的记录都插入完成后 从指针first所指向的记录开始一直读取到指针final所指向的记录 所得到的序列就是排序后的有序序列 8 2插入排序 22 8 2插入排序 23 8 2 4希尔排序 希尔排序方法又称为缩小增量排序 DiminishingIncrementSort 是对直接插入排序方法的改进 基本思想 将整个待排序的记录序列划分成若干个子序列 然后分别对每个子序列进行直接插入排序 这样可以减少参与直接插入排序的数据量 如此反复 当经过几次分组排序后 记录的排列已经基本有序 这个时候再对所有的记录进行一次直接插入排序 8 2插入排序 24 例如 162512304711233691831 第一趟希尔排序 设增量d 5 112312918162536304731 第二趟希尔排序 设增量d 3 918121123162531304736 第三趟希尔排序 设增量d 1 911121618232530313647 25 希尔排序是一种不稳定的排序方法 在待排序的记录数目较大的情况下 希尔排序方法一般要比直接插入排序方法快 其时间复杂度与所选取的增量序列有关 是所取增量序列的函数 介于O nlog2n 和O n2 之间 增量序列有多种取法 但应使增量序列中的值没有除1之外的公因子 并且增量序列中的最后一个值必须为1 从空间复杂度来看 与直接插入排序一样 希尔排序也只需要一个记录大小的辅助空间 用于暂存当前待插入的记录 8 2插入排序 26 8 3选择排序 选择排序 SelectionSort 的基本思想是 每一趟从待排序的序列中选出关键字最小的记录 顺序放在已排好序的子序列的最后 直到全部记录排序完毕 简单选择排序堆排序 27 基本思想是 将整个序列 假设含有n条记录 分为有序区和无序区 初始时有序区为空 无序区为整个待排序序列 第1趟排序 从无序区的n个记录中选取最小的记录与序列中的第一条记录交换位置 它做为有序区的第一条记录 此时无序区剩下n 1条记录 第2趟排序 从无序区的n 1条记录中选取最小的记录与序列中的第二条记录交换位置 它做为有序区的第二条记录 此时无序区剩下n 2条记录 第i趟排序 从无序区的n i 1条记录中选取最小的记录与序列中的第i条记录交换 它做为有序区的第i条记录 此时无序区剩下n i条记录 如此反复 n个记录的可经过n 1趟简单选择排序得到有序结果 8 3 1简单选择排序 8 3选择排序 28 假设排序过程中 待排记录序列的状态为 有序序列R 1 i 1 无序序列R i n 第i趟简单选择排序 从中选出关键字最小的记录 有序序列R 1 i 无序序列R i 1 n 29 初始 49386597761327 i 1 13 49 一趟 13 386597764927 i 2 27 38 六趟 132738496576 97 排序结束 13273849657697 k指示序列中最小数的位置j指示当前比较数的位置 30 简单选择排序算法简单 但是速度较慢 时间复杂度为O n2 并且是一种不稳定的排序方法 在排序过程中也只需要一个用来交换记录的暂存单元作为辅助空间 8 3选择排序 31 8 3 2堆排序 堆排序 HeapSort 是利用堆的特性进行排序 堆的定义如下 n个元素的序列为 K1 K2 Kn 当且仅当满足下列关系时 称之为堆 Ki K2i Ki K2i 1或Ki K2i Ki K2i 1 i 1 2 n 2 若将与此序列对应的一维数组看成是一棵完全二叉树按层次编号的顺序存储 则堆的含义表明 完全二叉树中所有非终端结点的值均不小于 或不大于 其左 右孩子结点的值 因此 堆顶元素的值必为序列中的最大值或最小值 即大顶堆或小顶堆 8 3选择排序 32 8 3选择排序 堆排序的基本思想是 对一组待排序的记录 首先把它们按堆的定义排成一个堆 将堆顶元素取出 然后把剩下的记录再排成堆 取出堆顶元素 依次下去 直到取出全部元素 从而将全部记录排成一个有序序列 33 8 3选择排序 实现堆排序需要解决两个问题 1 如何将一个无序序列建成一个堆 2 如何在输出堆顶元素之后 调整剩余元素成为一个新的堆 建堆就是把待排序的记录序列 R1 R2 Rn 按照堆的定义调整为堆 使父结点的关键字大于 或小于 子结点的关键字 为此 我们先把待排序数据初始次序置入完全二叉树的各个结点中 然后由下而上逐层进行父子结点的关键字比较并交换 直到使其最后满足堆的条件 建堆时是从最后一个非终端结点n 2开始的 34 例如 假定待排序的一组数据序列为 4236567867112736 8 3选择排序 35 40 55 49 73 81 64 36 12 27 98 例如 排序之前的关键字序列为 12 36 81 73 49 98 81 73 55 现在 左 右子树都已经调整为堆 最后只要调整根结点 使整个二叉树是个 堆 即可 98 49 40 64 36 12 27 36 对一组有n个记录的待排序序列进行按关键字递减排序时 先建立一个大顶堆 然后选取关键字值最大的堆顶记录与最后一个记录交换 再对前n 1个记录调整为一个新的大顶堆 如此反复直到排序结束 8 3选择排序 37 2019 12 30 38 堆排序对n较大的文件很有效 对记录数较少的文件不值得提倡 整个堆排序的时间复杂度为O nlog2n 堆排序仅需一个记录大小供交换用的辅助存储空间 对于存在相同关键字的记录的情况 堆排序是不稳定的 8 3选择排序 39 8 4交换排序 基本思想是 两两比较待排序记录的关键字 若发现两个记录的次序为逆序时 交换其存储位置 直到没有逆序的记录为止 冒泡排序快速排序 40 8 4交换排序 8 4 1冒泡排序 冒泡排序是一种简单的排序方法 基本思想 对所有相邻记录的关键字值进行比较 如果是逆序 r i r i 1 则交换其位置 经过多趟排序 最终使整个序列有序 41 假设在排序过程中 记录序列R 1 n 的状态为 第i趟起泡排序 无序序列R 1 n i 1 有序序列R n i 2 n n i 1 无序序列R 1 n i 有序序列R n i 1 n 比较相邻记录 将关键字最大的记录交换到n i 1的位置上 42 8 4交换排序 处理过程为 第一趟 从第一条记录r 1 开始 直到最后一条记录r n 对两两相邻的记录依此比较 若发现为逆序 则立即交换其位置 最后使这n条记录中关键字最大的记录 下沉 到最底部 既被交换到第n个位置上 它不参与下一趟排序 第二趟 从第一条记录r 1 开始 直到第n 1条记录r n 1 对两两相邻的记录依此比较 若发现为逆序 则立即交换其位置 最后使这n 1条记录中关键字最大的记录 下沉 到次底部 既被交换到第n 1个位置上 它不参与下一趟排序 如此反复 最多经过 n 1 趟冒泡排序 就可以使整个序列成为有序序列 43 38 49 76 97 13 97 27 97 97 30 13 76 76 76 13 65 27 30 65 27 65 30 13 49 49 49 27 30 13 38 27 38 30 38 44 例如 一组待排序的记录的关键字如下 要求按照关键字由小到大进行排序 4236567867112736 8 4交换排序 45 冒泡排序的时间复杂度为O n2 由于它的记录移动次数较多 故平均时间性能比直接插入排序要差得多 冒泡排序只需要一个记录的辅助空间 用来作为记录交换的中间暂存单元 冒泡排序是一种稳定的排序方法 8 4交换排序 46 8 4 2快速排序 快速排序 QuickSort 是对冒泡排序的一种改进 基本思想 通过一趟排序将待排序记录划分成两部分 使得其中一部分记录的关键字比另一部分记录的关键字小 然后再分别对这两部分记录进行这种排序 直到每个部分为空或只包含一个记录时 整个快速排序结束 8 4交换排序 47 8 4交换排序 待排序的序列 r s r s 1 r t 先任意选取一个记录 通常可选第一个记录r s 作为基准记录或称为支点 然后重新排列这些记录 将所有关键字较它小的记录都排到它的位置之前 将所有关键字较它大的记录都排到它的位置之后 由此可以将该基准记录所在的位置i作为分界线 将待排序记录序列划分成两个子序列 r s r i 1 和 r i 1 r t 这个过程称为一趟快速排序 一趟快速排序完成后得到前后两个子序列 可再分别对分割后的两个子序列进行快速排序 整个快速排序过程结束 48 s t low high 设R s 52为支点 将R high key和支点的关键字进行比较 要求R high key 支点的关键字 将R low key和支点的关键字进行比较 要求R low key 枢轴的关键字 high 23 low 80 high 14 low 52 例如 R 0 52 low high high high low 49 例如 待排序记录的关键字为 4236567867112736 8 4交换排序 50 8 4交换排序 51 首先对无序的记录序列进行 一次划分 之后分别对分割所得两个子序列 递归 进行快速排序 无序的记录序列 无序记录子序列 1 无序子序列 2 支点 一次划分 分别进行快速排序 52 完成一趟排序 273813 49 76976550 分别进行快速排序 13 27 38 49 5065 76 97 快速排序结束 1327384950657697 49 27 49 65 13 49 49 97 53 快速排序的时间复杂度平均为O nlog2n 当n较大时 这种算法是平均速度最快的排序算法 因此称为快速排序 快速排序是一种不稳定的排序方法 8 4交换排序 54 8 5归并排序 归并排序 MergingSort 归并 的含义是将两个或两个以上的有序序列合成一个新的有序序列 假设初始序列含有n个记录 则可看成是n个有序的子序列 每个子序列的长度为1 然后两两归并 得到n 2个长度为2 最后一个序列长度可能小于2 的有序子序列 再两两归并 得到n 2 2个长度为4 最后一个序列长度可能小于4 的有序序列 如此重复 直至得到一个长度为n的有序序列为止 每一次合并过程称为一趟归并排序 这种排序方法称为2 路归并排序 55 在内部排序中 通常采用的是2 路归并排序 即 将两个位置相邻的记录有序子序列 归并为一个记录的有序序列 有序序列R l n 有序子序列R l m 有序子序列R m 1 n 这个操作对顺序表而言 是轻而易举的 56 例如 52 23 80 36 68 14 s 1 t 6 52 23 80 52 23 52 23 52 80 36 68 14 36 68 36 68 14 36 68 14 23 36 52 68 80 23 57 例如 设待排序的记录序列为 4236567867112736 2 路归并排序中的核心操作是将一维数组中前后相邻的两个有序序列归并为一个有序序列 8 5归并排序 58 2 路归并排序算法的时间复杂度为O nlog2n 在排序时需利用一个与待排序数组同样大小的辅助数组 占用内存比前面介绍的算法多 2 路归并排序算法是稳定的 8 5归并排序 59 8 6基数排序 基数排序 RadixSorting 是和前面所述各类排序方法完全不同的一种排序方法 前面讨论的排序主要是通过关键字间的比较和移动记录这两种操作实现的 而基数排序不需要进行关键字间的比较 基数排序是借助多关键字排序的思想实现的 8 6 1多关键字的排序 60 8 6基数排序 例如 扑克牌中52张牌面的次序关系为 2 3 A 2 3 A 2 3 A 2 3 A每一张牌有两个 关键字 花色 和面值 2 3 A 且 花色 的地位高于 面值 在比较任意两张牌面的大小时 必须先比较 花色 若 花色 相同 则再比较面值 由此 将扑克牌整理成如上所述次序关系时 通常采用的办法是 先按不同 花色 分成有次序的四堆 每一堆的牌均有相同的 花色 然后分别对每一堆按 面值 大小整理有序 也可采用另一种办法 先按不同 面值 分成13堆 然后将这13堆牌自小至大叠在一起 3 在 2 之上 4 在 3 之上 最上面的是4张 A 然后将这付牌整个颠倒过来再按不同 花色 分成4堆 最后将这4堆牌按自小至大的次序合在一起 在最下面 在最上面 此时同样得到一付满足如上次序的牌 这两种整理扑克牌的方法便是两种多关键字的排序方法 61 为了实现多关键字排序 通常有两种方法 第一种方法是先对最高位关键字K0进行排序 将序列分成若干子序列 每个子序列中的记录都具有相同的K0值 然后分别对每个子序列按次高位关键字K1进行排序 按K1值不同再分成若干个更小的子序列 每个子序列中的记录都具有相同的K1值 依次重复 直至完成对Kd 1进行排序 最后将所有子序列依次连接在一起成为一个有序序列 这种方法称之为最高位优先 MostSignificantDigitFirst 法 简称MSD法 第二种方法是从最低位关键字Kd 1起进行排序 然后再对高一位的关键字Kd 2进行排序 依次重复 直到对K0进行排序后便成为一个有序序列 这种方法称之为最低位优先 LeastSiginifi cantDigitFirst 法 简称LSD法 8 6基数排序 62 8 6基数排序 MSD和LSD只规定按什么样的 关键字次序 来进行排序 而未规定对每个关键字进行排序时所用的方法 比较这两种方法 LSD要比MSD简单 因为LSD是对每个关键字都是整个序列参加排序 通过若干次 分配 和 收集 来实现排序 执行的次数取决于d的大小 而MSD需要处理各序列与子序列的独立排序问题 通常是一个递归问题 63 8 6 2链式基数排序 基数排序是借助于多关键字排序思想进行排序的方法 其基本操作是按关键字位进行 分配 和 收集 在基数排序的 分配 与 收集 操作过程中 为了避免数据元素的大量移动 通常采用链式存储结构存储待排序的记录序列 8 6基数排序 64 通常将关键字取值的数目称为基数 用RADIX表示 按LSD进行排序 对待排序的记录序列按照复合关键字从低位到高位的顺序交替地 分配 到RADIX个队列中后再 收集 如此重复d次 最终得到有序的记录序列 有些记录的关键字可以看成是由若干个关键字组合而成 即K K0K1 Kd 1 每个关键字Ki表示关键字的一位 其中K0为最高位 Kd 1为最低位 d为关键字的位数 8 6基数排序 65 下面举例说明基数排序过程 设待排序记录的关键字为 387 456 592 625 076 471 050 396 557 522 8 6基数排序 66 8 6基数排序 67 8 6基数排序 68 从基数排序的算法中容易看出 对于n个记录 假设每个记录含d个关键字 每个关键字的取值范围为r 则采用基数排序需进行d趟关键字的分配和收集 每趟运算时间复杂度为O n r 所以基数排序的时间复杂度为O d n r 由于d r是常数 当n较大时 基数排序的时间复杂度近似为O n 但n较小 d较大时 采用基数排序并不合适 只有当n较大 d较小时 基数排序才最为有效 这种排序方法的缺点是占用的存储空间较多 每个待排序的记录都需要加上指针域 基数排序是稳定的排序算法 8 6基数排序 69 8 7几种排序方法的比较 1 时间复杂度 直接插入排序