数据结构与算法 (10).ppt

第十章 内部排序 Chapter10 InternalSorting 排序又称分类 是计算机中最重要的操作 它是将一个数据元素 或记录 的任意序列排列成一个按关键字有序的序列 若待排序列中存在两个或以上关键字相等的记录 设Ki Kj 1 i j n 即排序前Ri在Rj前 若在排序后Ri仍在Rj前 则称排序是稳定的 稳定的排序方法 stablesortingmethod 排序 sorting 不稳定的排序方法 unstablesortingmethod 待排序列中存在两个或以上关键字相等的记录 设Ki Kj 1 i j n 即排序前Ri在Rj前 若在排序后Rj却在Ri前 则称排序是不稳定稳定的 内部排序 internalsorting 待排序列记录全部存放在计算机随机存储器中进行排序的过程称为内部排序 外部排序 externalsorting 待排序列记录数量太大 不能全部存放在计算机随机存储器中 排序过程中需对计算机外存进行访问 这种排序过程称为外部排序 1 比较操作 比较两个关键字值的大小的操作 排序过程中的两种基本操作 2 移动操作 将记录从一个位置移动到另一个位置的操作 待排序列的三种存储结构 1 顺序存储 存储在地址连续的一组存储单元中 以此为例 2 链式存储 存储在地址不连续的一组存储单元 链表 中 3 地址存储 记录顺序存储 另设关键字和记录地址排序 typedefstruct keytypekey elemtype typedefstruct elemtype elem intlength sqlist 10 1插入排序 一 直接插入排序 直接插入排序 straightinsertionsort 是一种最简单的排序方法 将记录一个个插入到已排序好的有序表中 从而得到长度增加的新的有序表 voidstraightinsertsort sqlist 排序性能分析 比较次数 最好情况 n 1最坏情况 n 2 n 1 2平均比较次数 n 4 n 1 4 二 折半插入排序 折半插入排序 binaryinsertionsort 与直接插入排序不同之处在于查找插入位置时不是用顺序查找 而是用折半查找 可见 直接插入排序的时间复杂度为O n2 但在待排序列有序的的情况下 直接插入排序的时间复杂度下降为O n 移动次数 最好情况 0最坏情况 n 4 n 1 2平均移动次数 n 4 n 1 4 折半插入排序的移动次数与直接插入排序相同 只是比较次数少了 因此其时间复杂度也为O n2 三 2 路插入排序 2 路插入排序目的是为了减少排序过程中移动记录的次数 代价是需要n个记录的辅助空间d 将r 1 赋值给d 1 将d看成循环的 其它记录均与d 1 比较 比其小则在d 1 前插入 反之则在d 1 后插入 2 路插入排序的移动次数大约为n2 2 因此其时间复杂度仍为O n2 四 表插入排序 表插入排序需附设一个指针域 通过改变指针的值来达到不移动记录而得到排序结果的目的 表插入排序是用改变指针来代替移动记录操作 因此其时间复杂度还为O n2 表插入排序的结果是形成了链表 因此查找时只能用顺序查找 为能使用折半查找 需对记录重新排序 但这不影响其时间复杂度 五 希尔排序 希尔排序 Shell smethod 又称为 缩小增量排序 diminishingincrementsort 是一种比较复杂的插入排序 希尔排序的思想是 用一定的增量间隔将待排序列分成多个组 每组都采用简单插入排序 排序完一遍后 缩小增量间隔 再对新的分组采用简单插入排序 反复此过程 直至增量间隔为1 即整个待排序列为一组时 执行一遍简单插入排序后结束 voidShellinsert sqlist 希尔排序的时间复杂度与增量序列有关 分析起来很复杂 有人认为为O n1 5 也有人认为为O n1 3 在以上插入排序中 除希尔排序为不稳定排序外 其余的都是稳定的排序 voidShellsort sqlist 10 2交换排序 一 起泡排序 起泡排序 bubblesort 也是一种最简单的排序方法 将相邻两记录一一比较 将关键字较小的记录交换在前面 反复此过程 直到待排序列有序为止 voidbubblesort sqlist 起泡排序也是一种稳定的排序 时间复杂度为O n2 二 快速排序 快速排序 quicksort 是对起泡排序的改进 将待排序列第一个元素 枢轴元素 pivot 放置到序列中的某个位置 使其前面的所有元素的关键字都小于它 后面的所有元素的关键字都大于它 再分别对枢轴元素前面和后面的两段待排序列采用快速排序方法 直至每一段都只剩下一个元素为止 intquickpass sqlist voidquicksort sqlist 快速排序是基于比较和交换的排序方法里最快的一种排序 其时间复杂度为O nlogn 但快速排序的效率不太稳定 在关键字均匀分布时 效率最高 在关键字有序时 效率将退化为O n2 如何解决这个难题呢 其实 我们仔细分析就可看出 效率低是因为枢轴元素的选取有问题 我们希望每次选取的枢轴元素都处于待排序列中间位置 但当待排序列有序时 枢轴元素的取值每次都是最大的或最小的 有鉴于此 我们能否考虑在枢轴元素选取时 与部分元素比较一下 选取它们中处于中间大小的元素与枢轴元素交换 作为新的枢轴元素 通常是将处于待排序列头部 尾部和中间的三个元素比较 从而得到新的枢轴元素 这种方法叫 三者取中法 它能很有效的防止快速排序效率的退化 在空间复杂度上 除静态数据外 由于递归的原因 栈的最大深度在最好的情况下为O logn 在最坏的情况下为n 在非递归算法中 每次都先对较短的子序列先进行排序能降低栈的深度 快速排序是不稳定排序 voidquicksort sqlist 快速排序的非递归算法如下 作业29 试证明 当待排序列已呈现出有序状态时 快速排序的时间复杂度为O n2 30 试以单链表为存储结构实现简单插入排序 第六次上机作业输入若干组长度各异的待排序列 分别用快速排序算法和改进的枢轴元素三者取中算法对待排序列进行排序 当待排子序列长度已小于20时 改用直接插入排序 利用时间函数验证三者取中算法在效率上的提高 提示 待排序列的长度一般应为5000以上 10 3选择排序 一 简单选择排序 简单选择排序 simpleselectionsort 同样也是一种最简单的排序方法 每次从待排序列中选出关键字最小记录作为有序序列中最后一个记录 直至最后一个记录为止 voidsimpleselectionsort sqlist 二 树形选择排序 借鉴体育比赛中淘汰赛的做法 将两两比赛过的优胜者推举出去与其它组的优胜者比赛 反复此过程 直到决出冠军为止 若能记住每次比赛的结果 则亚军的产生不必再经过此过程 只需将与冠军赛过的每一个运动员逐级进行比赛 即可得到亚军 这就是树形选择排序的思路 树形选择排序 treeselectionsort 又称为锦标赛排序 tournamentsort 是一种按锦标赛思 由于有不相邻元素交换 所以简单选择排序是不稳定的排序 其时间复杂度为O n2 树形选择排序除第一次外 每次都走了树的一条分支 故其时间复杂度为O nlogn 想进行的排序 将相邻记录两两分为一组进行比较 将关键字较小的记录送往上一层 参加与其它组关键字较小记录的比较 两两比较后再送往上层关键字较小记录 反复此过程 直到只剩下一个记录即为关键字最小记录 将待排序列中该最小记录处置为无穷大 则与其比较过的所有记录按层次逐级比较 直至找到下一个最小记录为止 反复此过程直至序列有序 三 堆排序 堆的定义 堆排序的思路 将待排序列建成堆 初始堆生成 后 则序列的第一个元素 堆顶元素 就一定是序列中的最大元素 将其与序列的最后一个元素交换 将序列长度减一 再将序列建成堆 堆调整 后 堆顶元素 树形排序需要2n 1个辅助空间 1964年J Willioms提出另外一种选择排序 堆排序 heapsort 仍是序列中的最大元素 再次将其与序列最后一个元素交换并缩短序列长度 反复此过程 直至序列长度为一 所得序列即为排序后结果 堆排序的结果为 12 26 32 58 63 74 85 91 那么 应如何建立初始堆 又如何进行堆调整呢 其实 由此例可以看出 建立初始堆就是多次进行堆调整的过程 voidheapadjust sqlist voidheapsort sqlist 堆排序只需一个辅助空间用于交换 其时间复杂度为O nlogn 堆排序是不稳定排序 10 4归并排序 归并排序 mergingsort 的思想是每次将两个或两个以上的有序表合并成一个较长的有序表 反复此过程 直到最终只剩下一个有序表为止 单个记录即是最初的有序表 voidmerge sqlist voidmergesort sqlist 以上给出的是二路归并排序的非递归算法 其实归并排序可以很方便的用递归程序实现 归并排序是一种稳定的排序方法 其时间复杂度为O nlogn 辅助空间为n 作业31 假设有n个值不同的元素存于数组A 1 n 中 另设一数组C 1 n 对每个元素A i C i 存放A中值小于A i 的元素的个数 则C i 0的元素即为最小元素 然后根据C的值大小将A中的元素重新排列 这种方法称为计数排序 试编程实现之 10 5基数排序 基数排序 radixsort 是和前面所介绍的排序方法 基于比较的排序方法 完全不同的一种排序方法 它是一种分配排序 多关键字排序 如52张扑克牌按以下规则排成有序 可以看出 牌点是决定大小的主要因数 3 4 10 J Q K A 2 花色则是决定大小的次要因数 Diamond Club Heart Spade 只有在牌点相同时 它才起作用 因此我们称牌点为高位关键字 花色为 D3 C3 H3 S3 D4 C4 HA SA D2 C2 H2 S2 一般的 设有n个记录序列 R1 R2 Rn 每个记录Ri均含有d个关键字 Ki1 Ki2 Kid 则称此序列对关键字 K1 K2 Kd 有序 是指序列中任意两个记录Ri和Rj 1 i j n 都满足有序关系 Ki1 Ki2 Kid Kj1 Kj2 Kjd 其中K1称为最高位关键字 Kd称为最低位关键字 那么应如何实现序列的多关键字排序呢 低位关键字 决定元素的大小主要看高位关键字 低位关键字只有在高位关键字相等时才发挥作用 LSD法 将待排序列依次按Kd Kd 1 K1进行排序得到有序序列 这种排序方法称为最低位优先法 LeastSignificantDigitfirst MSD法 将序列先按K1进行排序 则序列将分成若干子序列 每个子序列中的记录均具有相同的K1值 然后再分别对各子序列按K2进行排序 则序列将分成更多的子序列 反复此过程 直到全部子序列分别按Kd进行了排序后 再将所有子序列依次联接成一个有序序列 这种排序方法称为最高位优先法 MostSignificantDigitfirst MSD与LSD各有什么特点呢 MSD在排序时间上要比LSD快些 且每次对排序方法是否稳定没有要求 但操作起来相对复杂 因为序列将被分成若干个子序列 而LSD每次均对全部记录进行排序 但除按低位关键字排序对稳定性没有要求外 其后的所有排序方法均需是稳定的 LSD比较容易用多次分配和收集来实现 链式基数排序 基数排序是将关键字看成d个关键字复合而成 即按其基数rd所处位置的权值大小分成高 低位关键字 再应用多次分配 收集方法将待排序列排成有序序列 该方法又称为桶排序 bucketsort 待排序列用静态链表存储 是用2rd个指针来作为rd个桶的底和盖指针 每次分配即将n个记录按其Ki分配到各个桶中 收集时则按各桶顺序从上到下依次收集 待排序列 22 12 91 26 74 53 51 85 22 12 91 26 74 53 51 85 收集 91 51 22 12 53 74 85 26 收集 12 22 26 51 53 74 85 91 91 22 12 53 74 85 26 51 10 6前面介绍的各种内部排序方法的比较 一次分配的时间为O n 一次收集的时间为O rd 故基数排序的时间复杂度为O d n rd 基于比较的排序方法 最好的时间复杂度是O nlogn 下面介绍一种公式分组