各种经典排序算法

本节基本内容与要求 基本内容顺序查找 二分查找 二叉树查找以及散列表上查找及算法思想排序的基本概念以及选择 插入 交换和归并四类排序的基本思想和算法要求掌握线性表 树和散列表 或称哈希表 的查找方法及算法实现以及各种查找方法的应用熟练掌握选择 插入 交换和归并四类排序的基本思想和算法 1 4内部排序 一 基本概念二 插入排序三 交换排序四 选择排序五 归并排序 一 基本概念 1 排序的功能 将一个数据元素 或记录 的任意序列 重新排成一个按关键字有序的序列 例如 下列是一组记录对应的关键字序列 52 49 80 36 14 58 61 23 97 75 调整为 14 23 36 49 52 58 61 75 80 97 2 排序的定义 假设含n个记录的序列为 R1 R2 Rn 其相应的关键字序列为 K1 K2 Kn 这些关键字相互之间可以进行比较 即在它们之间存在着这样一个关系 Kp1 Kp2 Kpn按此固有关系将上式记录序列重新排列为 Rp1 Rp2 Rpn 的操作称作排序 3 排序的基本操作 排序的概念 就是要整理文件中的记录 使之按关键字递增 或递减 次序排列起来 排序过程的组成步骤 首先比较两个关键字的大小 然后将记录从一个位置移动到另一个位置 对记录的关键字大小进行比较将记录从一个位置移动到另一个位置当待排序记录的关键字均不相同时 则排序结果是唯一的 否则排序的结果不一定唯一 4 排序的稳定性 若有 R1 Ri Rj 且关键字 Ki Kjij排序后 Ri Rj 则称该排序结果具有稳定性 在待排序的文件中 若存在多个关键字相同的记录 经过排序后这些具有相同关键字的记录之间的相对次序保持不变 该排序方法是稳定的 若具有相同关键字的记录之间的相对次序发生变化 则称这种排序方法是不稳定的 内部排序 是指在排序的整个过程中 数据全部存放在计算机的内存储器里 并且在内存储器里调整数据的位置 当文件很大以致内存不足以存放全部数据时 在排序过程中需要对外存进行存取访问 称这种借助于外存储器进行排序的方法为外部排序 注意 内排序适用于记录个数不很多的小文件 外排序则适用于记录个数太多 不能一次将其全部记录放入内存的大文件 5 排序的分类 每次将一个待排序的记录 按其关键字大小插入到前面已经排好序的子文件中的适当位置 直到全部记录插入完成为止 把新元素 未排序的元素的关键字 逐个插入正在增长的顺序表中 寻找插入位置的方法 线性插入排序对半插入排序希尔排序 二 插入排序 有序序列L r 1 i 1 L r i 无序序列L r i n 有序序列L r 1 i 无序序列L r i 1 n 1 线性插入排序 基本思想 每步将一个待排序的元素按其大小插入到前面已排序的数据中的适当位置 重复该工作 直至有序区包含所有元素 方法 具体方法 先将第一个数据看成是一个有序的子序列 然后从第2个数据起逐个插入到这个有序的子序列中去 相应的元素要移动 3 将L r i 插入到L r j 1 的位置上 2 将L r j 1 i 1 中的所有记录均后移一个位置 1 在L r 1 i 1 中查找L r i 的插入位置 L r 1 j L r i L r j 1 i 1 该算法适合于n较小的情况 时间复杂度为O n2 待排元素序列 53 2736156942第一次排序 2753 36156942第二次排序 273653 156942第三次排序 15273653 6942第四次排序 1527365369 42第五次排序 152736425369 线性插入排序示例 对于有n个数据元素的待排序列 插入操作要进行n 1次 例 voidinsertSort RedTypeL intn inti j for i 2 i n i L 0 L i 作为监视哨for j i 1 L 0 key L j key j L j 1 L j 记录后移L j 1 L 0 插入 插入算法 方法 Ki与Ki 1 Ki 2 K1依次比较 直到找到应插入的位置 哨兵 监视哨 哨兵 监视哨 有两个作用作为临时变量存放R i 当前要进行比较的关键字 的副本 在查找循环中用来监视下标变量j是否越界 R 0 R 1 R 2 R 3 R 4 R 5 6206157315620157376152073367152033671520 直接插入排序的程序 include stdio h definen5intar n intc t voidd insort a inta n inti j for i 2 i0 main inti printf 请输入数据 for i 1 i n i scanf d 运行结果 请输入数据 5060204080排序后的序列 20 40 50 60 80 性能分析 最好情况 原始记录按关键字有序排列 O n 比较 的次数 最坏情况 原始记录按关键字逆序排列 O n2 比较 的次数 0 移动 的次数 移动 的次数 结论 适用原始数据基本有序或数据量不大的情况 希尔排序 Shell smethod 又称为 缩小增量排序 本质上讲是插入排序 它是对线性插入排序的改进 其基本思想是 先取一个小于n的整数d1并作为第一个增量 将文件的全部记录分成d1个组 所有距离为d1倍数的记录放在同一个组中 在各组内进行直接插入排序 然后取第二个增量d2 d1 重复上述的分组和排序 直至所取的增量dt 1 dt dt 1 d2 d1 为止 此时 所有的记录放在同一组中进行直接插入排序 2希尔插入排序 算法思想 如何选择增量序列才能产生最好的排序效果 这个问题至今没有得到解决 希尔本人最初提出取d1 n 2 di 1 di 2 dt 1 t log2n 希尔插入排序 步骤 1 首先选取一个整数d1 n n为待排序数据的个数 作为两个数据之间的距离 这样把全部数据分成d1个组 凡是距离为d1的数据放在一个组里 在各组内进行内部排序 直到各组排好序为止 2 从上述的结果序列出发 再选择d2 d1 重复上面的分组与排序工作 3 依次取di 1 di 直到dm 1 设一共需要m次分组 即所有数据放在一组中排序为止 此时 全部数据便按次序排好了 设待排序共有10个记录 其关键字分别为47 33 61 82 71 11 25 47 57 02 增量序列取值依次为5 3 1 希尔插入排序 过程 希尔排序实质上还是一种插入排序 其主要特点是 每一趟以不同的增量进行排序 在每趟的插入排序中 记录的关键字是和同一组中的前一个关键字进行比较 所以关键字较小的记录在排序过程中是作跳跃式的移动 另外 由于开始时增量的取值较大 每组中记录较少 故排序比较快 随着增量值的逐步变小 每组中的记录逐渐变多 但由于此时记录已基本有序了 因次在进行最后一趟增量为1的插入排序时 只需作少量的比较和移动便可完成排序 从而提高了排序速度 希尔插入排序 特点 希尔排序比直接插入排序的平均性能要好 在最好情况 原始记录按关键字有序排列 下 移动次数为0 比较次数界于n n2之间 在最坏情况 原始记录按关键字逆序排列 下 移动次数和比较次数接近n2 在平均情况下 移动次数和比较次数在O n1 3 左右 好于直接插入排序 希尔插入排序 性能效率 例1 19希尔排序的程序 include stdio h definemax10intdata max 1 intindex max 1 inti voidshell sort a inta max 1 inti j n m skip intalldone for i 1 i1 skip skip 2 do alldone 1 for j 1 j max skip j i j skip n index i m index j if a n a m index i m index j n alldone 0 while alldone 0 main printf 请输入数据 for i 1 i max i scanf d 运行结果 请输入数据 194111174743133731231941111747431337312311131719233137414347希尔排序的分析较为复杂 因为它的时间是所取 增量 序列的函数 这涉及到一些数学上尚未解决的难题 增量序列可以有各种取法 但需注意 应使增量序列中的值没有除1以外的公因子 并且最后一个增量值必须等于1 2 希尔排序 三 交换排序 两两比较待排序记录的关键字 发现两个记录次序相反时即进行交换 直到没有反序的记录为止 冒泡排序快速排序 假设在排序过程中 记录序列L r 1 n 的状态为 第i趟冒泡排序 无序序列L r 1 n i 1 有序序列L r n i 2 n n i 1 无序序列L r 1 n i 有序序列L r n i 1 n 比较相邻记录 将关键字最大的记录交换到n i 1的位置上 7 3 1冒泡排序 基本思想和过程 voidBubbleSort SqList L for i L length i 1 i for j 1 jr j 1 r j Swap L r j L r j 1 时间性能分析 比较次数 最坏 n 1 n 2 1 最好 n 1移动次数 最坏 3 n 1 n 2 1 最好 0 7 3 1冒泡排序 算法和性能分析 2 5 5 3 1 5 7 9 8 9 i 7 i 6 for j 1 jr j 1 r j 1 3 i 2 7 3 1冒泡排序 改进 voidBubbleSort SqList L i L length while i 1 定位第i个位置的记录lastExchangeIndex 1 for j 1 jr j 1 r j Swap L r j L r j 1 lastExchangeIndex j i lastExchangeIndex 7 3 1冒泡排序 改进算法 最好情况 记录按关键字有序排列 只需进行一趟冒泡 比较 的次数 最坏情况 记录按关键字逆序排列 需进行n 1趟冒泡 比较 的次数 0 移动 的次数 移动 的次数 n 1 7 3 1冒泡排序 性能分析 首先对无序的记录序列进行 一次划分 通过一趟排序将待排序列分成两部分 使其中一部分记录的关键字均比另一部分小 再分别对这两部分排序 以达到整个序列有序 无序的记录序列 无序记录子序列 1 无序子序列 2 枢轴 一次划分 分别进行快速排序 7 3 2快速排序 基本思想 快速排序 目标 找一个记录 以它的关键字作为 枢轴 凡其关键字小于枢轴的记录移至该记录之前 反之 移至该记录之后 一趟排序之后 无序序列L r low high 将被分割成两个部分 L r low i 1 和L r i 1 high 且L r j L r i L r j low j i 1 枢轴 i 1 j high 快速排序 方法 关键字通常取第一个记录的值为基准值 方法 附设两个指针i和j 初值分别指向第一个记录和最后一个记录 设关键字为key 首先从j所指位置起向前搜索 找到第一个小于基准值的记录与基准记录交换 然后从i所指位置起向后搜索 找到第一个大于基准值的记录与基准记录交换 重复这两步直至i j为止 初始值465513429451770 快速排序一趟算法 初始值465513429451770 175513429451770 175513429455570 基准X 46 17513429455570 175134294945570 175134294945570 46 第一趟135174246945570 快速排序例 初始值465513429451770 第二趟513174246705594 第三趟513174246557094 第四趟513174246557094 快速排序 步骤 1 令指针L 1 R n 即分别指向A1和An 2 自尾端开始进行比较 将AR与AL比较 若AL AR 则数据就不交换 此时固定L 即L指针不动 调整尾指针 使R R 1 继续比较 直至AL AR时为止 将AR与AL交换位置 并修改左指针 使L L 1 3 将AL与AR比较 若AL AR 则调整左指针 使L L 1 R指针不动 继续比较 直至AL AR时为止 将AL与AR交换位置 并修改右指针R 使R R 1 4 重复 2 3 步骤 直到从两边开始的扫描在中间相遇 即L R指针重合于中间某一个元素 此时该元素即在排序的序列中找到了自己合适的位置 并且此元素将原序列分成了前后两个子集 虽然此时这两个子集还是无序的 但前一个子集的所有元素均小于后一个子集的所有元素 这称为一趟 设L r low 46为枢轴 在调整过程中 设立两个指针 low和high 之后逐渐减小high或增加low 并保证 将L r high 和枢轴的关键字进行比较 要求L r high 枢轴的关键字 将L r low 和枢轴的关键字进行比较 要求L r low 枢轴的关键字 L r high 枢轴且L r low 枢轴 否则进行记录的 交换 快速排序算法 voidquicksort intr intleft intright inti left j right intx r i while i x 递归调用右子区间 快速排序的时间主要耗费在划分操作上 对长度为k的区间进行划分 共需k 1次关键字的比较 最坏情况是每次划分选取的基准都是当前无序区中关键字最小 或最大 的记录 划分的结果是基准左边的子区间为空 或右边的子区间为空 而划分所得的另一个非空的子区间中记录数目 仅仅比划分前的无序区中记录个数减少一个 因此 快速排序必须做n 1次划分 第i次划分开始时区间长度为n i 1 所需的比较次数为n i 1 i n 1 故总的比较次数达到最大值 n n 1 2 O n2 快速排序 时间分析 在最好情况下 每次划分所取的基准都是当前无序区的 中值 记录 划分的结果是基准的左 右两个无序子区间的长度大致相等 总的关键字比较次数 O nlogn 因为快速排序的记录移动次数不大于比较的次数 所以快速排序 最坏时间复杂度应为O n2 最好时间复杂度为O nlogn 平均时间复杂度为O nlogn 快速排序 时间分析 快速排序在系统内部需要一个栈来实现递归 若每次划分较为均匀 则其递归树的高度为O logn 故递归后需栈空间为O logn 最坏情况下 递归树的高度为O n 所需的栈空间为O n 因为快速排序的划分次数在logn n之间 所以快速排序的 最坏空间复杂度应为O n 最好空间复杂度为O logn 平均空间复杂度为O logn 快速排序 空间分析 若待排记录的初始状态为按关键字有序时 快速排序将退化为冒泡排序 其时间复杂度为O n2 因此 快速排序适用于原始数据杂乱无章的倾向 辅助空间数量为递归调用所开辟的栈空间 7 3 2快速排序 适用范围 结论 快速排序的时间复杂度为O nlogn 且适用于原始数据杂乱无章的情况 快速排序是非稳定的 快速排序的程序 include stdio h definen10intar n 1 inti l1 intquick1 a l r inta n 1 intl r 指针 intl1 intr1 w l1 l r1 r w a l1 do while a r1 w voidq sort a l r inta n 1 intl r intl1 if l r l1 quick1 a l r q sort a l l1 1 q sort a l1 1 r main printf 请输入数据 n for i 1 i n i scanf d 运行结果 请输入数据 42237411655894369987排序后的序列 11233642586574879499 7 3 2快速排序 过程 7 4选择排序 简单选择排序 堆排序 假设排序过程中 待排记录序列的状态为 有序序列L r 1 i 1 无序序列L r i n 第i趟简单选择排序 从中选出关键字最小的记录 有序序列L r 1 i 无序序列L r i 1 n 7 4 1简单选择排序 基本思想和过程 四 选择排序 直接选择排序又称为简单选择排序 是一种简单直观的排序方法 从待排序的所有记录中 选取关键字最小的记录 并将它与原始序列中的第一个记录交换 然后从去掉了关键字最小记录的剩余记录中选择关键字最小的记录将它与原始记录序列的第二个记录交换位置 以此类推 直到序列中全部记录排序完毕 算法 对记录序列x 0 x n 1 进行直接选择排序voidselectsort elemtypex intn inti j small elemtypeswap for i 0 i n 1 i small i for j i 1 j n j if x j key x small key small j if small i swap x i X i x small X small swap 对n个记录进行简单选择排序 所需进行的关键字间的比较次数总计为 移动记录的次数 最小值为0 最大值为3 n 1 7 4 1简单选择排序 算法时间性能分析 堆就是一个关键字序列 并且这n个关键字的序列K1 K2 Kn要满足以下性质 堆性质 就是 Ki K2i且Ki K2i 1或者Ki K2i且Ki K2i 1 2 堆排序 堆的定义 正堆 逆堆 12 36 27 65 40 34 98 81 73 55 49 是正堆 12 36 27 65 40 14 98 81 73 55 49 不是堆 1234567891011 当把这个序列存入一个向量并把它看作是一棵完全二叉树的存储结构时 堆就是这样一棵二叉树 任一非叶结点的关键字均不小于 或不大于 其左右孩子结点的关键字 2 堆排序 12 36 27 65 49 81 73 55 40 34 98 是堆 14 不 12345678 最大值 a 堆顶元素取最大值大根堆 b 堆顶元素取最小值小根堆 堆排序基本思想 因为堆顶是最大的数 所以当把一个关键字序列排成一个大根堆时 就很容易地找到最大的数 它就在序列的第一个位置上然后把这个最大的数与最后一个记录交换 这时 最后一个记录就是关键字最大的记录了 对于剩下的关键字序列 我们仍然把它排成一个大根堆 然后再把第一个记录 当前堆中的堆顶 与当前堆的最后一个记录交换 这时 在整个序列后面就有了两个有序的关键字 从小到大 重复这样的过程 就可以把有序区不断扩大直到全部关键字都进入有序区 直到排序完成 堆的构造 无序序列r 1 n 构成的完全二叉树 从它最后一个非叶子结点 第n 2个元素 开始直到根结点为止 逐步进行调整即可将此完全二叉树构成堆 调整 与其左右子树根结点值比较 取其中大的进行交换 堆的构造例 4655134294051770 12345678 70 17 5 94 42 13 55 46 12345678 对调 对调 42 17 5 94 70 13 55 46 12345678 对调 对调 13 13 堆的构造例 4655134294051770 42 13 5 94 70 17 55 46 12345678 对调 55 55 对调 42 13 5 55 70 17 94 46 12345678 对调 46 46 对调 堆的构造例 4655134294051770 42 13 5 55 70 17 46 94 12345678 对调 46 46 对调 42 13 5 55 46 17 70 94 12345678 成堆 堆的构造例 4655134294051770 46 55 13 42 70 94 05 17 初始无序结点 从42开始调整 46 55 13 70 42 94 05 17 将以13为根的子树调整成堆 46 55 17 70 42 94 05 13 将以55为根的子树调整成堆 堆的构造例 4655134294051770 调整成堆算法 voidSIFT intr inti intn 调整r 1 n 中结点r i 使成为一个堆 intj intT T r i j 2 i j为i结点的左孩子序号while j n if j n i j T 堆排序 由给定的无序序列构造堆将堆顶元素与堆中最后一个元素交换将最后一个元素从堆中删除将余下的元素构成完全二叉树重新调整成堆反复进行 直到堆空 堆排序过程示例 94 13 5 55 46 17 70 42 94 70 5 42 46 17 55 13 94 70 55 42 13 17 46 5 94 70 55 46 13 17 42 5 94 70 55 46 42 17 13 5 94 70 55 46 42 17 13 5 94 70 55 46 42 17 13 5 堆排序结果 堆排序过程 94 13 5 55 46 17 70 42 94 70 5 42 46 17 55 13 94 70 55 42 13 17 46 5 94 70 55 46 13 17 42 5 94 70 55 46 42 17 13 5 94 70 55 46 42 17 13 5 94 70 55 46 42 17 13 5 第一趟结果 第二趟结果 第三趟结果 第四趟结果 第五趟结果 第六趟结果 第七趟结果 堆排序算法 voidheapsort intr intn 堆排序 intt for inti n 2 i 0 i 将r调整成堆SIFT r i n for i n 1 i 0 i t r 0 r 0 r i r i t SIFT r 0 i 1 i 0 堆排序的程序 include stdio h definemm8inta mm 1 intk voidshift a l m voidheapsort a inta mm 1 inti x for i mm 2 i 1 i shift a i mm 从第开始进行筛选建堆 for i mm i 2 i x a 1 a 1 a i a i x 将堆顶元素和堆中最后一个元素交换 shift a 1 i 1 调整第一个元素使之重又成为堆 main printf 请输入数据 n for k 1 k mm k scanf d 五 基数排序 前面介绍的几种排序方法都是按数据元素 或记录关键字 值的大小进行排序的而多关键字排序是一种按组成数据元素或关键字的各位值进行排序的方法 基数排序借助的就是这种思想 它属于分布式排序 也称口袋排序 基数排序是把逻辑关键字看成由若干个子关键字复合而成的 假设有n个关键字 r1 r2 rn 需进行排序 每个关键字由d元组 k1k2k3 kd 子关键字组成 k1是关键字值的最高位 kd是关键字值的最低位 其基数为rd 五 基数排序 前面介绍的几种排序方法都是按数据元素 或记录关键字 值的大小进行排序的多关键字排序是一种按组成数据元素或关键字的各位值进行排序的方法 基数排序借助的就是这种思想 基数排序属于分布式排序 也称口袋排序 桶子法 基数排序法是属于稳定性的排序时间复杂度为O nlog r m 其中r为所采取的基数 而m为堆数 在某些时候 基数排序法的效率高于其它的比较性排序法 基数排序的方式可以采用 LSD Leastsignificantdigital 的排序方式由键值的最右边开始MSD Mostsignificantdigital 由键值的最左边开始 以LSD为例 假设原来有一串数值如下所示 73 22 93 43 55 14 28 65 39 81 73 22 93 43 55 14 28 65 39 81 首先根据个位数的数值 在走访数值时将它们分配至编号0到9的桶子中 接下来将这些桶子中的数值重新串接起来 成为以下的数列 81 22 73 93 43 14 55 65 28 39 81 22 73 93 43 14 55 65 28 39 接着再进行一次分配 这次是根据十位数来分配 接下来将这些桶子中的数值重新串接起来 成为以下的数列 整个数列已经排序完毕 14 22 28 39 43 55 65 73 81 93 如果排序的对象有三位数以上 则持续进行以上的动作直至最高位数为止 LSD的基数排序适用于位数小的数列 如果位数多的话 使用MSD的效率会比较好 MSD的方式恰与LSD相反 是由高位数为基底开始进行分配 其他的演算方式则都相同 基数排序 排序前先将待排序元素置于一数组r 1 r n 中存储 每个结点除存放排序码的值外 还有一个指向下一个结点的指针 即下一个结点的下标值 排序时从最低位kd开始 直到最高位k1 把关键字依其子关键字的值分配到rd个队列中去 同一队列中的元素用指针链接 同时队头和队尾各用一个指针指示 该头 尾指针分别存放在两个数组f ra1 f ra2 和e ra1 e ra2 中 ra1和ra2为子关键字ki的取值范围 每经过一次分配后 都将各队列中的元素按次序收集在一起 经过d次的分配和收集后即得到了按序排列的序列 基数排序 例如 若关键字是十进制数值 将全部数据放在数组r中 然后按下列步骤进行 1 初态 设置10个队列 并且使其均为空 2 分配 依次从数组r中取出每个关键字 第i遍处理时 考察该关键字右起第i位数字 即第i个子关键字 设其值位k 则把该关键字插入第k个队列 数组r全部处理完后 全部数据被分配到队列0 队列9 3 收集 从队列0开始 依队列0 队列9的头 尾指针 修改数组r中各关键字的指针 即将这次分配完的关键字依逻辑次序再链接起来 4 循环 重复以上 1 3 步 若关键字有d位数字 就需要执行d遍 基数排序 考察由3位十进制数字组成的关键字 则其值在0 k 999范围内 可把每一个十进制数看成一个逻辑关键字k k由三个子关键字 k1 k2 k3 组成 其中k1是百位数 k2是十位数 k3是个位数 由此分解得到的每个关键字ki都在相同的范围内 0 ki 9 排序是先从最低位k3开始 按k3的大小分成若干组 每组中k3值相同 然后将各组数据收集在一起 下次再按k2大小排序 如此重复 直到对k1排序后 整个数据集即成为有序序列 基数排序 例1 22基数排序过程的程序设有10个十进制数 179 208 234 056 800 178 651 245 006 958 该数列数值范围在0 999之间 因此子关键字位数d 3 个位数为低关键字位 百位数为高关键字位 关键字值得范围为0 9 基数为10 进行基数排序过程如图1 61所示 r 1 r 2 r 3 r 4 r 5 r 6 r 7 r 8 r 9 r 10 179 208 234 056 800 178 651 245 006 958 a 初始状态 b 按最低关键字位值分配 800 651 234 245 056 006 208 178 958 179 c 第一次收集 d 按次低关键字位值分配 800 006 208 234 245 651 056 958 178 179 e 第二次收集 f 按最高关键字位值分配 006 056 178 179 208 234 245 651 800 958 g 第三次收集后得排序结果图1 61基数排序示例 基数排序的程序 include stdio h definera10 definera29 defined3 definen10intkeyval ra1 keyval ra2 intpn 1 pn n structrnode intkey 4 keyval intnext 0 next n structrnoder n 1 intrsort r structrnoder n 1 intj k t i intf 10 e 10 0 9 intp p 1 for i d i 1 i for j ra1 j ra2 j f j 0 头指针初始化 while p 0 分配 k r p key i if f k 0 f k p elser e k next p e k p p r p next j 0 收集 while f j 0 j j 1 p f j t e j while j ra2 j j 1 if f j 0 r t next f j t e j r t next 0 return p main intp inti j printf 请输入数据 for i 1 i n i for j 1 j 3 j scanf d 基数排序 运行结果 请输入数据 179220832344056580061787651824590061095801792 2083 2344 0565 8006 1787 6518 2459 00610 9580 排序后的数据 00605617817920823424