第9章：排序.ppt

1 了解排序的定义和各种排序方法的特点 熟悉各种方法的排序过程及其依据的原则 2 掌握各种排序方法的时间复杂度的分析方法 能从 关键字间的比较和移动次数 分析排序算法的平均情况和最坏情况的时间性能 熟悉各种算法的适用场合 3 理解排序方法 稳定 或 不稳定 的含义 弄清楚在什么情况下要求应用的排序方法必须是稳定的 本章学习要求 第9章 排序 9 1排序的基本概念 9 2插入排序 9 3选择排序 9 4交换排序 9 5归并排序 9 1概述 一 排序的定义 二 内部排序和外部排序 三 内部排序方法的分类 一 什么是排序 排序 整理文件中的记录 将一组杂乱无章的数据排列成一个按关键字有序的序列 排序是计算机内经常进行的一种操作 其目的是将一组 无序 的记录序列调整为 有序 的记录序列 例如 将下列关键字序列 52 49 80 36 14 58 61 23 97 75 调整为 14 23 36 49 52 58 61 75 80 97 一般情况下 假设含n个记录的序列为 R1 R2 Rn 其相应的关键字序列为 K1 K2 Kn 这些关键字相互之间可以进行比较 即在它们之间存在着这样一个关系 Kp1 Kp2 Kpn 按此固有关系将上式记录序列重新排列为 Rp1 Rp2 Rpn 的操作称作排序 数据表 datalist 待排序数据对象的有限集合 关键字 key 通常数据对象有多个属性域 即多个数据成员组成 其中有一个属性域可用来区分对象 作为排序依据 该域即为关键字 每个数据表用哪个属性域作为关键字 要视具体的应用需要而定 即使是同一个表 在解决不同问题的场合也可能取不同的域做关键字 主关键字 如果在数据表中各个对象的关键字互不相同 这种关键字即主关键字 按照主关键字进行排序 排序的结果是唯一的 次关键字 数据表中有些对象的关键字可能相同 这种关键字称为次关键字 按照次关键字进行排序 排序的结果可能不唯一 即若待排序的序列中存在两个或两个以上关键字相等的记录 则排序所得到的结果不唯一 排序算法的稳定性 如果在对象序列中有两个对象ri和rj 它们的关键字ki kj 且在排序之前 对象ri排在rj前面 如果在排序之后 对象ri仍在对象rj的前面 则称这个排序方法是稳定的 否则称这个排序方法是不稳定的 二 内部排序和外部排序 若整个排序过程不需要访问外存便能完成 则称此类排序问题为内部排序 反之 若参加排序的记录数量很大 整个序列的排序过程不可能在内存中完成 则称此类排序问题为外部排序 排序的时间开销 排序的时间开销是衡量算法好坏的最重要的标志 排序的时间开销可用算法执行中的数据比较次数与数据移动次数来衡量 各节给出算法运行时间代价的大略估算一般都按平均情况进行估算 对于那些受对象关键字序列初始排列状态及对象个数影响较大的 需要按最好情况和最坏情况进行估算 衡量排序方法的标准 排序时所需要的平均比较次数排序时所需要的平均移动次数排序时所需要的平均辅助存储空间 三 内部排序的方法 内部排序的过程是一个逐步扩大记录的有序序列长度的过程 大多数排序方法在排序过程中将出现如图所示 有序 和 无序 两个区域 经过一趟排序 有序序列区 无序序列区 有序序列区 无序序列区 其中有序区内的记录已按关键字递增有序排列 而无序区内为待排记录 通常称 使有序区中记录数目增加一个或几个 的操作过程为 一趟排序 按何种策略扩大有序区域将导致不同的排序方法 内部排序方法大致可分下列几种类型 插入类 交换类 选择类 归并类 待排序的记录序列可以用顺序表表示 也可以用链表表示 本章讨论的排序算法一律以顺序表 数组 为操作对象 待排记录的数据类型定义如下 definen1000 待排顺序表最大长度 typedefstruct intkey 关键字项datatypeotherinfo 其它数据项 rectype 记录类型 rectypeR n R为记录类型的数组 将无序子序列中的一个记录 插入 到有序序列中 从而以达到扩大有序区的长度的目的 一趟排序完成一个记录的插入 每一趟都将无序区中的第一个记录按其关键字值的大小插入到有序区中的适当位置 直到无序区中的全部记录都插完为止 一趟直接插入排序的基本思想 在对记录序列R 1 n 的排序过程中 区段R 1 i 1 中的记录已按关键字非递减的顺序排列 将R i 插入到有序序列R 1 i 1 中 使区段R 1 i 中的记录按关键字非递减顺序排列 9 2插入排序方法 有序序列R 1 i 1 R i 无序序列R i n 一趟直接插入排序的基本思想 有序序列R 1 i 无序序列R i 1 n 直接插入排序 基于顺序查找 不同的具体实现方法导致不同的算法 希尔排序 基于逐趟缩小增量 由此实现一趟插入排序的步骤为 在R 1 i 1 中查找R i 的插入位置 即确定j 1 j i 使得R 1 j key R i key R j 1 i 1 key将R j 1 i 1 中的记录后移一个位置 将R i 插入到j 1的位置 为了避免在查找过程中判别循环变量是否出界 设置R 0 为监视哨 并方便在查找的同时进行 记录后移 如动画演示所示 例 47 33 61 82 72 11 25 47 初始状态 47 33618272112547 第1遍 i 2 33 3347 618272112547 第2遍 i 3 61 334761 8272112547 第3遍 i 4 82 33476182 72112547 第4遍 i 5 72 3347617282 112547 第5遍 i 6 11 113347617282 2547 第6遍 i 7 25 11253347617282 47 第7遍 i 8 47 1125334747 617282 监视哨R 0 直接插入排序算法实现 利用 顺序查找 实现 在R 1 i 1 中查找R i 的插入位置 算法的实现要点 1 从R i 1 起向前进行顺序查找 监视哨设置在R 0 2 对于在查找过程中找到的哪些关键字不小于R i key的记录 并在查找的同时实现记录向后移动 从R i 1 起向前进行顺序查找 监视哨设置在R 0 R 0 R i 设置 哨兵 循环结束表明R i 的插入位置为j 1 R 0 j R i while R 0 key R j key R j 1 R j j 从后往前找 j i 1 插入位置 R j 1 R 0 对于在查找过程中找到的哪些关键字不小于R i key的记录 并在查找的同时实现记录向后移动 while R 0 key R j key R j 1 R j j R j 1 R 0 R 0 j R i j i 1 上述循环结束后可以直接进行 插入 插入位置 令i 2 3 n 实现整个序列的排序 for i 2 i n i R 0 R i j i 1 while R 0 key R j key R j 1 R j 记录后移R j 1 R 0 插入到正确位置 监视哨R 0 的作用 1 进入查找循环之前 它保存了R i 的副本 使得不致于因为记录的后移而丢失R i 中的内容 2 在while循环或for循环中监视下标变量j是否越界 避免循环内部每次都要检测j是否越界 直接插入排序的时间复杂度分析 从上述排序过程可见 排序中的两个基本操作是 关键字间的 比较和 记录的 移动 因此排序的时间性能取决于排序过程中这两个操作的次数 从直接插入排序的算法可见 这两个操作的次数取决于待排记录序列的状态 当待排记录处于 正序 即记录按关键字递增排列 的情况时 所需进行的关键字比较和记录移动的次数最少 每趟排序比较1次 即R 0 和R i 1 比较 记录移动2次 Cmin n 1 Mmin 2 n 1 反之 当待排记录处于 逆序 即记录按关键字递减排列 的情况时 所需进行的关键字比较和记录移动的次数最多 每趟进行i次比较 每趟移动次数 每趟除了上面的两次移动外 还要有i 1次的后移一个位置 若待排记录序列处于随机状态 则可以最坏和最好的情况的平均值作为插入排序的时间性能的量度 一般情况下 直接插入排序的时间复杂度为O n2 9 2 2希尔排序 希尔排序又称 缩小增量排序 它的基本思想是 先对待排序列进行 宏观调整 待序列中的记录 基本有序 时再进行直接插入排序 希尔排序 ShellSort 希尔排序方法又称为 缩小增量 排序 该方法的基本思想是 先将整个待排对象序列按照一定间隔分割成为若干子序列 分别进行直接插入排序 然后缩小间隔 对整个对象序列重复以上的划分子序列和分别排序工作 直到最后间隔为1 此时整个对象序列已 基本有序 进行最后一次直接插入排序 将记录序列分成若干子序列 分别对每个子序列进行插入排序 其中 d称为增量 它的值在排序过程中从大到小逐渐缩小 直至最后一趟排序减为1 例如 将n个记录分成若干个子序列 R 1 R 1 d R 1 2d R 1 kd R 2 R 2 d R 2 2d R 2 kd R d R 2d R 3d R kd R k 1 d 例1 162512304711233691831 第一趟希尔排序 设增量d 5 112312918162536304731 第二趟希尔排序 设增量d 3 918121123162531304736 第三趟希尔排序 设增量d 1 911121618232530313647 1234567891011 1234567891011 1234567891011 1234567891011 d 3 d 2 123456 开始时d 间隔值 的值较大 子序列中的对象较少 排序速度较快 随着排序进展 d值逐渐变小 子序列中对象个数逐渐变多 由于前面工作的基础 大多数对象已基本有序 所以排序速度仍然很快 D常选质数 d1 n 2 d2 d1 2 di 1 从上述例子的排序过程可见 由于希尔排序在前几趟的排序过程中 关键字较大的记录是 跳跃式 地往后移动 从而使得在进行最后一趟插入排序之前序列中记录的关键字已基本有序 只需作少量关键字比较和移动记录 由此减少了整个排序过程中所需进行的 比较 和 移动 的次数 9 3选择排序 选择排序基本思想 原理 每一趟在待排序的记录中选出关键字最小的记录 依次放在已经排序好的记录序列的最后 直至全部记录排完为止 分为直接选择排序和堆排序 直接选择排序思想 第一趟排序时在无序区R 0 R n 1 中选出关键字最小的记录 将它和R 0 交换 第二趟排序时在无序区R 1 R n 1 中选出关键字最小的记录 将它和R 1 交换 第i趟排序时在无序区R i 1 R n 1 中选出关键字最小的记录 将它和R i 1 交换 以此类推 简单选择排序 假设排序过程中 待排记录序列的状态为 有序序列R 1 i 1 无序序列R i n 第i趟简单选择排序 从中选出关键字最小的记录 有序序列R 1 i 无序序列R i 1 n 21 25 49 25 16 08 012345 21 25 i 1 49 25 16 25 16 08 49 08 25 49 21 i 2 i 3 08 16 25 25 21 初始 最小者08交换21 08 最小者16交换25 16 最小者21交换49 21 第一趟结果 第二趟结果 i 2 第2趟 时选择排序的过程 k赋初值为i 只要R j key R k key 就把j赋给k 每次循环结束如果找到最小的关键字 则将j赋值给k 然后判断i和k是否相等 不等则将R k 和R i 交换即可 123456 49 16 08 25 49 21 08 25 25 21 ikj 49 25 08 25 16 21 ikj 49 25 25 25 16 25 ikj 16 25 双层循环 49 25 08 25 16 21 012345 ikj k指示当前序列中最小者 第2趟选择排序结果 直接选择排序的算法描述 voidSelectSort rectypeR inti j k rectypetemp for i 0 i n 1 i 进行n 1趟选择排序 k i for j i 1 j n j if R j key R k key k j if k i 交换R i 和R k temp R i R i R k R k temp 在当前无序区中选择关键字最小的记录R k 直接选择排序的关键字比较次数与对象的初始排列无关 第i趟选择具有最小关键字对象所需的比较次数总是n i次 因此 总的关键字比较次数为 由于每趟选择后可能要进行两个记录的交换 而每次交换都要进行3次记录的移动 因此最大移动次数为3 n 1 最少移动次数为0 时间复杂度为O n2 直接选择排序是一种不稳定的排序方法 时间性能分析 9 4交换排序 1 起泡排序 2 快速排序 3 时间分析 交换排序 交换排序的基本思想 两两比较待排序对象的关键字 如果发生逆序 即排列顺序与排序后的次序正好相反 则交换之 直到所有对象都排好序为止 常用的有起泡排序和快速排序 第1趟 对所有记录 纵向序列 从下到上每相邻两个记录的关键字进行比较 如果这两个记录的关键字不符合排序要求 则进行交换 这样一趟做完 将关键字最小者放在最上方的位置上 第2趟 对剩下的n l个待排序记录重复上述过程 又将一个关键字放于最终位置 上方第2个位置 反复进行n l次 可将n l个关键字对应的记录放至最终位置 剩下的即为关键字最大的记录 它放在最下方的位置上 因此 排序至多需要n 1趟排序 如果某一趟排序中没有记录交换 则说明排序可以提早结束 为此 算法设计时可以定义一个变量noswap 根据它的值判断需不需要提前结束循环 起泡排序的基本思想 将关键字按纵向排列 然后自下而上地对每两个相邻的关键字进行比较 如果逆序 r j 1 key r j key 则交换两个记录 起泡排序 例 下标12345678 初始序列 4931638575152649 第1趟 1549316385752649 1526493163857549 1526314949 638575 第2趟 第3趟 第4趟 第5趟 第6趟 第7趟 1526314949 637585 1526314949 637585 1526314949 637585 1526314949 637585 noswap 待排序的9个记录的排序码序列为 312 126 272 226 8 165 123 12 28 使用冒泡 下沉 排序算法进行的排序过程如下图所示 时间性能分析 最好的情况 关键字在记录序列中递增有序 只需进行一趟起泡 比较 的次数 最坏的情况 关键字在记录序列中逆序有序 需进行n 1趟起泡 比较 的次数 0 移动 的次数 移动 的次数 n 1 起泡排序需要一个附加变量以实现记录值的对换 或者用R 0 起泡排序是一个稳定的排序方法 冒泡排序使用说明 该算法是专门针对已部分排序的数据进行排序的一种排序方法 如果在你的数据清单中只有一两个数据是乱序的话 用这种算法就是最快的排序算法 如果你的数据清单中的数据是随机排列的 那么这种方法可能就成了最慢的算法了 例如初始序列是3 6 8 9 15 20 1 则只需一趟冒泡即可实现排序 但是对于20 1 3 6 8 9 15 则需要扫描6趟才能完成排序 原因 扫描方向的单一性导致了两种情况的不对称性 快速排序 快速排序则是任意选定一个关键字介于 中间 的记录通过一趟排序使剩余记录分成两个子序列分别继续排序 通常称该记录为 基准或枢轴R p 一趟排序也称为一次划分 假设一趟快速排序之后基准记录的位置为i 则得到的无序记录子序列 1 R s i 1 中记录的关键字均小于基准记录的关键字 得到的无序记录子序列 2 R i 1 t 中记录的关键字均大于基准记录的关键字 由此这两个子序列可分别独立进行快速排序 快速排序 首先对无序的记录序列进行 一次划分 之后分别对分割所得两个子序列 递归 进行快速排序 无序的记录序列 无序记录子序列 1 无序子序列 2 基准 一次划分 分别进行快速排序 一趟快速排序 一次划分 目标 找一个记录 以它的关键字作为 基准 凡其关键字小于基准的记录均移动至该记录之前 反之 凡关键字大于基准的记录均移动至该记录之后 致使一趟排序之后 记录的无序序列R s t 将分割成两部分 R s i 1 和R i 1 t 且R j key R i key R j key s j i 1 基准 i 1 j t 基准选取 可以取待排序列中任何一个记录作为基准 但为方便起见 通常取序列中第一个记录R s 为基准 以它的关键字作为划分的依据 划分可如下进行 设置两个指针low和high 分别指向待排序列的低端s和高端t 若R high keyR s key 则将它移动至枢轴记录之后 并为避免枢轴来回移动 可先将枢轴R s 暂存在数组的闲置分量R 0 或者变量pivot中 s t low high 设R s 52为基准 将R high key和基准的关键字进行比较 要求R high key 基准的关键字 向左扫描找到比基准小的就覆盖R low 然后low 开始向右扫描 将R low key和基准的关键字进行比较 要求R low key 基准的关键字 向右扫描找比基准大的就覆盖R high 然后high 向左扫描 如此反复左右交替扫描 当low high时就找到了基准的位置 high 23 low 80 high 14 low 52 例 R 0 52 low high high high low 可见 经过 一次划分 将关键字序列 52 49 80 36 14 58 61 97 23 75调整为 23 49 14 36 52 58 61 97 80 75 在调整过程中 设立了两个指针 low和high 它们的初值分别为 s和t 之后逐渐减小high 增加low 并保证R high key 52和R low key 52 否则进行记录的 交换 其实是覆盖 快速排序的算法是一个递归函数 因此算法中必须引入一对参数s和t作为待排序区域的上下界 在算法的递归调用过程执行中 这两个参数随着 区域的划分 而不断变化 快速排序的核心就是一次划分 或者叫一趟快速排序 例如 关键字序列 52 49 80 36 14 75 58 97 23 61 经第1趟快速排序之后为 23 49 14 36 52 75 58 97 80 61 经第2趟快速排序之后为 14 23 49 36 52 61 58 75 80 97 经第3趟快速排序之后为 14 23 36 49 52 58 61 75 80 97 快速排序具有较好的时间复杂度 平均时间复杂度为O nlog2n log2n趟 每趟n i次比较 1 i n 1 当待排序列为递增有序时 快速排序比冒泡排序更恶化 冒泡只需要进行一趟排序即可O n 而快速排序则需要进行n 1次递归调用 时间复杂度 O n2 若待排记录的初始状态为按关键字递减时 快速排序将蜕化为起泡排序 其时间复杂度为O n2 为避免出现这种情况 需在进行一次划分之前 进行 预处理 即 先对R s key R t key和R s t 2 key 进行相互比较 然后取关键字为 三者之中 的记录为基准记录 最好的情况 基准居中 即每次划分后左右两个子序列长度基本一致 此时时间复杂度 O nlogn 快速排序算法 intPARTITION rectypeR intl inth 返回划分后被定位的基准记录的位置 对无序区R l 到R h 做划分 inti j rectypetemp i l j h temp R i 初始化 temp为基准do while R j key temp key 递归处理右区间 QUICKSORT 9 5归并排序 归并排序的基本操作是将两个或两个以上的记录有序序列归并为一个有序序列 最简单的情况是 只含一个记录的序列显然是一个有序序列 经过 逐趟归并 使整个序列中的有序子序列的长度逐趟增大 直至整个记录序列为有序序列止 2 路归并排序则是归并排序中的一种最简单的情况 它的基本操作是将两个相邻的有序子序列 归并 为一个有序序列 如图所示 这个操作对顺序表而言是极其容易实现的 只要依关键字从小到大进行 复制 即可 归并排序的算法思想和过程 算法思想 假设初始表含有n个记录 则可看成是n个有序的子表 每个子表的长度为1 然后两两归并 得到 n 2 个长度为2或1的有序子表 再两两归并 如此重复 直至得到一个长度为n的有序子表为止 归并排序过程 一次2路归并 voidmerge rectypeR rectypeR1 intlow intmid inthigh R low R mid 与R mid 1 R high 是两个有序文件 结果放在R1 low R1 high inti j k i low j mid 1 k low while i mid voidmergepass rectypeR rectypeR1 intlength 一趟归并 inti j i 0 i指向第一对子文件的起始点 while i 2 length 1 n 归并长度为length的两个子文件 merge R R1 i i length 1 i 2 length 1 一次归并 i i 2 length 置下一个一次归并的起始位置 if i length 1 n 1 merge R R1 i i length 1 n 1 else 子文件个数为奇数 剩一个不需要归并 直接复制到R1中 for j i j n j R1 j R j 剩下一个有序子表 其长度小于lengh 本算法结束后tabg中的有序段的长度为2 length 一趟归并算法 voidmergesort rectypeR intlength length 1 初始时有序段的长度为1 while length n 有序段的长度小于待排序元素的个数 继续归并 mergepass R R1 length 一趟归并 结果在R1中 length 2 length 有序段的长度翻倍 mergepass R1 R length 再次归并 结果在R中 length 2 length 有序段的长度翻倍 归并排序算法 归并排序要做log2n上限整数趟归并 每趟归并所花时间为O n 故2路归并算法时间复杂度为 O nlog2n 14 6各种排序方法的综合比较 一 时间性能 1 平均的时间性能 平均时间复杂度为O nlog2n 快速排序和归并排序 平均时间复杂度为O n2 直接插入排序 起泡排序和简单选择排序 2 当待排记录序列按关键字顺序有序时 最好情况 3 大致有序 大部分递增个别无序 选择冒泡排序和直接插入排序 4 N较大且随机分布时 快速排序和归并排序时间复杂度相对较低 快速排序作为首选 其次是归并排序 5 递减时 尽量选择归并 时间复杂度最低 6 简单选择排序和归并排序的时间性能不随记录序列中关键字的分布而改变 跟初始分布无关 直接插入排序和起泡排序能达到O n 的时间复杂度 快速排序的时间性能蜕化为O n2 二 空间性能 指的是排序过程中所需的辅助空间大小 1 所有的排序方法 包括 直接插入 希尔排序 起泡和简单选择 的空间复杂度为O 1 2 快速排序为O log2n 为递归程序执行过程中 栈所需的辅助空间 3 归并排序所需辅助空间最多 其空间复杂度为O n 三 排序方法的稳定性能 稳定的排序方法指的是 对于两个关键字相等的记录 它们在序列中的相对位置 在排序之前和经过排序之后 没有改变 排序之前 Ri K Rj K 排序之后 Ri K Rj K 例如 排序前 56 34 47 23 66 18 82 47 若排序后得到结果 18 23 34 47 47 56 66 82 则称该排序方法是稳定的 若排序后得到结果 18 23 34 47 47 56 66 82 则称该排序方法是不稳定的 选择排序 快速排序 和希尔排序是不稳定的排序方法 直接插入排序 冒泡排序和归并排序是稳定的排序 回顾与分析 直接插入排序 简单的插入排序 每次比较后最多移掉一个逆序 因此与冒泡排序的效率相同 但它在速度上还是要高点 这是因为在冒泡排序下是进行值交换 而在插入排序下是值移动 所以直接插入排序将要优于冒泡排序 直接插入法也是一种对数据的有序性非常敏感的一种算法 在有序情况