排序是组织数据最基本的运算排序的方法也很多本章给出了几种典型的排序方法见下表
排序类别 插入排序 交换排序 选择排序 归并排序 分配排序
排序方法 直接插入 冒泡法 直接选择 * 归并排序 箱排序
希尔排序 * 快速排序(分治法) * 堆排序 * 基数排序
这 五类 内部排序方法的基本思想排序过程算法实现时间和空间性能的分析以及各种排序方法的比较和选择都是本章内容带*号的几种排序方法的基本思想及排序过程是本章需重点理解掌握的部分同时这四个排序算法的实现是难点总之这章的内容很多实在是多太多可是大家都不怕
一基本概念( 识记 )
记录 中用于某一 项 可用来标识一个记录则称为 关键字项 该数据项的值称为 关键字 (注意其区别)
排序 就是要整理文件中的记录使之按关键字递增(或递减)次序排列起来当待排序记录的关键字均不相同时则排序结果是唯一的否则排序的结果不一定唯一如果在待排序文件中存在多个关键字相同的记录经过排序后这些具有相同关键字的记录之间的相对次序保持不变则称这种排序方法是稳定的否则排序算法是不稳定的
这里的 稳定性的含义 就是指用某种排序方法在对文件进行排序后 关键字 相同的 记录 的 相对次序的稳定性 稳定是 针对 所有 输入实例 而言的只要存在一个输入实例在排序后关键字相同记录的相对次序发生变化就足以认定该排序算法是不稳定的
排序过程中整个文件在内存中处理不涉及数据的内外存交换则称之为内部排序(内排序)反之若存在数据的内外存交换则称之为外排序
内部排序 方法可分 五类 插入排序选择排序交换排序归并排序和分配排序
评价排序算法好坏的标准 主要有 两条 执行 时间 和所需的 辅助空间 另外算法的复杂程序也是要考虑的一个因素
二插入排序( 综合应用 )
插入排序 的基本思想是每次将一个待排序的记录 按其 关键字 大小插 入到 前 面已经排好序的子文件中的适当 位 置直到全部记录插入完成为止
直接插入排序算法比较容易理解其中的哨兵的作用应当深刻理解并能运用
哨兵 (监视哨)有两个作用 一是作为临变量存放R[i] (当前要进行比较的关键字)的副本 二是在查找循环中用来监视下标变量j是否越界
实际上一切为简化边界条件而引入的附加结点(元素)均可称为哨兵
直接插入 排序 是稳定的 也就是相同关键字的记录的相对位置在排序后不发生改变
直接插入排序 的时间复杂度在不同输入实例时是不同的最好情况是文件初态为正序此时算法的时间复杂度为O(n)最坏情况是文件为反序时间复杂度为O(n^)算法的 平均时间复杂度也是O(n^) 该算法的空间复杂度为O()是就地排序
对于一个给定的输入实例我们应当能够写入直接插入排序的排序过程
对于 希尔排序 要记住它的算法是 不稳定 的
三交换排序( 综合应用 )
交换排序 的基本思想是 两两比较 待排序记录的关键字发现两个记录次序相 反 时 即 进行交 换 直到没有反序的记录为止
冒泡排序 的基本思想是将每个记录R[i]看作是重量为R[i]key的气泡根据轻泡不能在重泡之下的原则从 最后 一个记录(最下方的记录) 开始往上扫 描 两两 进行 比较 凡扫描到违反上述原则的气泡就进行交换保证 轻 气 泡 在 上 如此反复进行直到任何两个气泡都达到轻者在上重者在下为止
冒泡排序比较简单其算法也容易理解冒泡排序算法是稳定的 主要的难点还是快速排序
快速排序 其基本思想是将原问题分解为若干个规模更小但结构与原问题相似的子问题;递归地解这些子问题然后将这些解组合为原问题的解由于采用了分治的策略因此通常称为 分治法 (教材中写为冶我拍拍脑袋想想大概是作者笔误吧这个冶字好象与Conquer搭不上边)
分治法有三个步骤分解求解组合
分解 就是在原记录中任选一个记录作为基准以此基准把当前无序区划分为左右两个较小的子区间并使左边的记录关键字均小于等于基准记录的关键字右边子区间中的记录关键字均大于这个基准记录的关键字分解的过程其实是一次粗略排序的过程即它 只做一件事 把整个无序区 排列 成三部分小于等于基准的部分基准和大于等于基准的部分
求解 就是递归调用了也就是在左子区间和右子区间里再进行分解求解直到不用再分就可以求解
组合 什么也不做求出的解就是组合的结果
所以在分治法中最关键的一步就是分解算法的实现即确定当前无序区中的基准记录所在位置以便递归调用时能够知道当前无序区的区间
那么在分治法中分解一步选哪个记录作为基准呢? (选定一个基准后就将以它为界把关键字比它大的记录移到右边比它小的移到左边)当然可以随意选定一个为了算法的简明可以选无序区的第一个记录作为基准算法的实现也不复杂如果我们能够写出算法每次划分后的状态则理解算法的实现也就很容易了
对于快速排序其时间主要耗费在划分操作上最坏的情况是每次划分选取的基准都是当前无序区中关键字最小(或最大)的记录这时快速排序必须作n次划分时间复杂度为O(n^)这种情况就是文件已按递增序或递减序排列在最好的情况下每次划分所选的基准都是当前无序区的中值记录此时的时间复杂度为O(nlgn)由于出现最坏情况的输入实例概率极小因此它的 平均性能接近于它的最好时间复杂度 也是O(nlgn)
快速排序 算法是 非稳定 的比如[ ]这个序列排序后的结果为
三选择排序( 简单应用 )
选择排序 的基本思想是每一趟从 待排 序的 记录 中 选 出关键字 最小 的记录顺序存放已排好的子文件的最后(最前)直到全部记录排序完毕
直接选择 排序容易理解其 时间复杂度为O(n^) 就地排序算法是 不稳定 的
本来知道直接选择法就行了可是就是有人吃饱了撑的又弄出了 堆排序有什么好呢就是因为它更省时间更完美就象上面的分治法
为了弄清堆排序是什么东西还得先知道堆是什么东西
堆就是一个关键字序列 并且这n个关键字的序列KKKn要满足以下性质( 堆性质 )就是 Ki≤Ki且Ki≤Ki+ 或者 Ki≥Ki且Ki≥Ki+ 当把这个序列存入一个向量并把它看作是一棵完全二叉树的存储结构时堆就是这样一棵二叉树任一非叶结点的关键字均不大于(或不小于)其左右孩子结点的关键字(是不很象一堆从小到大(或从大到小)的关键字堆起来的塔?)
如这棵二叉树的根结点(堆顶)是树上所有结点关键字中最小和最大者则称这两种堆为 小根堆 和 大根堆 堆中任一子树亦是堆
知道了这些就可以讨论堆排序了其实堆排序就是运用了上述堆的性质这里以大根堆为例因为堆顶是最大的数所以当把一个关键字序列排成一个 大根堆 时就很容易地找到 最大 或最小的数它就 在序列的第一个位置上 然后把这个最大的数与最后一个记录交换这时最后一个记录就是关键字最大的记录了这是确定的对于 剩下 的关键字序列我们仍然把它排成一个大根堆然后再把第一个记录(当前堆中的堆顶)与当前堆的最后一个记录交换这时在整个序列后面就有了两个有序的关键字(从小到大)重复这样的过程就可以把有序区不断扩大直到全部关键字都进入有序区直到排序完成
这个算法主要是 建立初始堆和重建堆 的过程它的时间复杂度 最坏情况下为O(nlgn)而平均性能接近于最坏性能 堆排序不适宜于记录数较少的文件 堆排序 是 就地排序 是 不稳定 的
对于给定的序列用堆排序的过程主要是通过画完全二叉树来演示
四归并排序( 领会 )
归并就是将若干个已排序的文件合成一个有序的文件这个算法容易理解其时间复杂度 无论在最好还是最坏的情况下都是O(nlgn) 它不是就地排序因为用到了一个辅助向量 归并排序是稳定的
五分配排序( 领会 )
分配排序的思想是不通过关键字的比较来进行排序而是根据关键字的取值来进行分配
箱排序的平均时间复杂度是线性的O(n)
基数排序是对箱排序的改进和推广其基本思想是从低位到高位依次对关键字进行箱排序要保证基数排序是正确的就必须保证 除第一趟外各趟箱排序是稳定的
我们要能够对一给定序列写出其基数排序的过程
六各种排序方法的比较和选择( 简单应用 )
这一节还比较重要的主要是简单应用就是给定一类记录其数目以及其他条件让我们选择一个最合适的排序算法这就要了解各种排序方法的优缺点
选择排序方法时应 综合考虑下列因素
待排序的记录数目n;(n较大的就要用时间复杂变为O(nlgn)的排序方法所以也要记一下算法的时间复杂度)
记录的大小(规模);(记录很大的话要用大量时间和空间来移动它们因此最好用链表作为存储结构而快速排序和堆排序在链表上难于实现)
关键字的结构及其初始状态;(比如实数就不能使用箱排序和基数排序)
对稳定性的要求(这一点要多多注意记住哪些排序算法是稳定的)
语言工具的条件(有的语言没有提供指针类或递归算法则不易用归并快速排序和基数排序等算法);
存储结构;
