数据结构-排序.ppt

数据结构 数据结构 C 语言版 排序 目录 排序 将数据元素的一个任意序列 重新排列成一个按关键字有序的序列 概念 例 将关键字序列 52 49 80 36 14 58 61 23 调整为 14 23 36 49 52 58 61 80 一般情况下 假设含n个记录的序列为 R1 R2 Rn 其相应的关键字序列为 K1 K2 Kn R1 R2 R3 R4 R5 R6 R7 R8 K1 K2 K3 K4 K5 K6 K7 K8 这些关键字相互之间可以进行比较 即在它们之间存在着这样一个关系 在次讨论升序 Kp1 Kp2 Kpn Kp1 Kp2 Kp3 Kp4 Kp5 Kp6 Kp7 Kp8 按此固有关系将上式记录序列重新排列为 Rp1 Rp2 Rpn 的操作称作排序 Rp1 Rp2 Rp3 Rp4 Rp5 Rp6 Rp7 Rp8 若Ki为记录Ri的主关键字 则排序结果惟一 若Ki为记录Ri的次关键字 则排序结果可以不惟一 因为会有相同的关键字 例 设排序前的关键字序列为 52 49 80 36 14 58 36 23若排序后的关键字序列为 14 23 36 36 49 52 58 80 则排序方法是稳定的 若排序后的关键字序列为 14 23 36 36 49 52 58 80 则排序方法是不稳定的 内部排序和外部排序 若整个排序过程不需要访问外存便能完成 则称此类排序问题为内部排序 反之 若参加排序的记录数量很大 整个序列的排序过程不可能在内存中完成 则称此类排序问题为外部排序 本章不讨论 内部排序的方法 内部排序的过程是一个逐步扩大记录的有序序列的过程 有序序列区 无序序列区 有序序列区 无序序列区 排序方法分类 基于不同的 扩大 有序序列长度的方法 内部排序方法大致可分下列几种类型 依次将无序子序列中的一个记录 插入 到有序序列中 从而增加记录的有序子序列的长度 通过 交换 无序序列中的记录从而得到其中关键字最小或最大的记录 并将它加入到有序子序列中 以此方法增加记录的有序子序列的长度 从记录的无序子序列中 选择 关键字最小或最大的记录 并将它加入到有序子序列中 以此方法增加记录的有序子序列的长度 通过 归并 两个或两个以上的记录有序子序列 逐步增加记录有序序列的长度 基数排序是一种基于多关键字排序的思想 将单关键字按基数分成 多关键字 进行排序的方法 目录 插入排序 一趟直接插入排序的基本思想 实现 一趟插入排序 可分三步进行 3 将R i 插入 复制 到相应的位置上 2 记录后移一个位置 1 在有序区中查找R i 的插入位置 简单排序方法 直接插入排序 i 2 38 49 38 7趟排序 1趟排序 2趟排序 voidInsertSort SqList i if L r i key L r i 1 key InsertSort 排序过程 先将序列中第1个记录看成是一个有序子序列 然后从第2个记录开始 逐个进行插入 直至整个序列有序 在R 1 i 1 中查找R i 的插入位置 对于在查找过程中找到的那些关键字不小于R i key的记录 在查找的同时实现记录向后移动 插入R i L r 0 L r i 复制为监视哨L r i L r i 1 for j i 2 L r 0 key L r j key j L r j 1 L r j 记录后移L r j 1 L r 0 插入到正确位置 比较次数和移动次数均约为 T n O n 算法评价 时间复杂度 比较次数 移动次数 0 最好的情况 待排序记录按关键字从小到大排列 正序 比较次数 移动次数 最坏的情况 待排序记录按关键字从大到小排列 逆序 一般情况 待排序记录是随机的 取平均值 空间复杂度 S n O 1 直接插入排序是稳定排序 第二趟希尔排序 第三趟分组 设d3 1 希尔排序 缩小增量排序 基本思想 对待排序列先作 宏观 调整 再作 微观 调整 排序过程 先取一个正整数d1 n 把所有相隔d1的记录放在一组内 组内进行直接插入排序 然后取d2 d1 重复上述分组和排序操作 直至di 1 即所有记录放进一个组中排序为止 其中di称为增量 例 第一趟希尔排序 第三趟希尔排序 第一趟分组 设d1 5 49386597761327495504 13274955044938659776 第二趟分组 设d2 3 例 待排序列为34 81 72 42 10 28 52 77 33 13 109 4 42 89 增量di分别取5 3 1 则排序过程如下 d0 53481724210285277331310944289 子序列分别为 34 28 109 81 52 4 72 77 42 42 33 89 10 13 第一趟排序结果 2844233103452724213109817789 第二趟排序结果 1343428134233724252898177109此时 序列基本 有序 对其进行直接插入排序 得到最终结果 4101328333442425272778189109 希尔排序特点 分组不是简单的 逐段分割 而是将相隔某个增量的记录组成一个子序列 增量序列取法希尔最早提出的选法是d1 n 2 di 1 di 2 克努特 Knuth 提出的选法是di 1 di 1 3 还有其他不同的取法 如何选择增量序列以产生最好的排序效果 至今仍没有从数学上得到解决 最后一个增量值必须为1 希尔排序可提高排序速度1 记录跳跃式前移 在进行最后一趟排序时 已基本有序 2 分组后n值减小 n2更小 而T n O n2 所以T n 从总体上看是减小了 目录 3 重复直到 在一趟排序过程中没有进行过交换记录的操作 或 仅第一二个交换过 为止 冒泡排序算法 改进 交换排序 冒泡排序 排序过程 1 比较第一个记录与第二个记录 若关键字为逆序则交换 然后比较第二个记录与第三个记录 依次类推 直至第n 1个记录和第n个记录比较为止 第一趟冒泡排序 结果关键字最大的记录被安置在最后一个记录上 2 对前n 1个记录进行第二趟冒泡排序 结果使关键字次大的记录被安置在第n 1个记录位置 第一趟排序 49 38 49 97 76 97 97 13 97 97 27 97 97 49 97 3849657613274997 38496513274976 第二趟排序 384913274965 第三趟排序 3813274949 第四趟排序 13273849 第五趟排序 132738 第六趟排序 for j 1 j n j if r j 1 r j r j r j 1 for j 1 j n 1 j if r j 1 r j r j r j 1 for i n i 1 i i while i 1 while i n i k VoidBubbleSort SqList L k j 交换的位置 k 1 一般情况下每经过一趟 起泡 i减1 但并不是每趟都如此 例 i 6 i 2 i 1 算法评价 时间复杂度 最好情况 正序 比较次数 n 1移动次数 0T n O n 最坏情况 逆序 比较次数 移动次数 T n O n2 空间复杂度 S n O 1 稳定性 稳定排序 快速排序 设数组A中存放了n个数据元素 low为数组的低端下标 high为数组的高端下标 从数组A中任意取一个元素 一般是取A low 作为中间元素 调整数组A中各元素的位置 使得 关键字比中间元素小的数据元素排在中间元素前面关键字比中间元素大的数据元素排在中间元素后面 这样以中间元素为轴 将数组A中的元素划分成两个子数组 然后再对这两个子数组分别进行快速排序 例 一趟快速排序过程示例r 0 r 1 r 2 r 3 r 4 r 5 r 6 r 7 r 8 r 9 r 10 4328397698694515828r 0 r 1 r 2 r 3 r 4 r 5 r 6 r 7 r 8 r 9 r 10 4328397698694515828 lowhigh从high向前搜索小于r 0 key的记录 28 将其赋值给low指向的位置 r 0 r 1 r 2 r 3 r 4 r 5 r 6 r 7 r 8 r 9 r 10 4328283976986945158 lowhigh从low向后搜索大于r 0 key的记录 76 将其赋值给high指向的位置 r 0 r 1 r 2 r 3 r 4 r 5 r 6 r 7 r 8 r 9 r 10 4328283998694515876 lowhigh从high向前搜索小于r 0 key的记录 4 将其赋值给low指向的位置 4328283949869515876 lowhigh从low向后搜索大于r 0 key的记录 98 将其赋值给high指向的位置 从high向前搜索小于r 0 key的记录4328283946998515876 lowhigh 4328283946998515876 lowhighhigh low 划分结束 将r 0 key的值赋值给low high 指向的位置 2828394436998515876 voidQSort SqList L intlow inthigh 对顺序表L中的子序列L r low high 进行快速排序if low high 长度大于1 QSort pivotloc Partition L low high 对L r low high 进行一次划分 QSort L low pivotloc 1 对低子序列递归排序 pivotloc是枢轴位置 QSort L pivotloc 1 high 对高子序列递归排序 第一次调用函数Qsort时 待排序记录序列的上 下界分别为1和L length voidQuickSort SqList QuickSort 快速排序的时间分析 假设一次划分所得枢轴位置i k 则对n个记录进行快排所需时间 其中Tpass n 为对n个记录进行一次划分所需时间 若待排序列中记录的关键字是随机分布的 则k取1至n中任一值的可能性相同 T n Tpass n T k 1 T n k 由此可得快速排序所需时间的平均值为 设Tavg 1 b 则可得结果 结论 快速排序的时间复杂度为O nlogn 一次划分所需时间和表长成正比 若待排记录的初始状态为按关键字有序时 快速排序将蜕化为起泡排序 其时间复杂度为O n2 所以快速排序适用于原始记录排列杂乱无章的情况 快速排序是平均速度最大的一种排序方法 快速排序是一种不稳定的排序 在递归调用时需要占据一定的存储空间用来保存每一层递归调用时的必要信息 目录 选择排序 直接选择排序 是以降低数据元素的移动次数为排序思路 排序过程 首先通过n 1次关键字比较 从n个记录中找出关键字最小的记录 将它与第一个记录交换 再通过n 2次比较 从剩余的n 1个记录中找出关键字次小的记录 将它与第二个记录交换 重复上述操作 共进行n 1趟排序后 排序结束 假设排序过程中 待排记录序列的状态为 有序序列R 1 i 1 无序序列R i n 第i趟简单选择排序 从中选出关键字最小的记录 有序序列R 1 i 无序序列R i 1 n 例 待排序列 352845551968 初始状态352845551968i 1 19 2845553568元素19和35交换i 2 1928 45553568元素35和45交换i 3 192835 554568元素45和55交换i 4 18243545 5568i 5 1824354555 68i 6 182435455568 j if L r j key L r k key k j j i 1 for i 1 i L length i 例 初始 49386597761327 i 1 13 49 一趟 13 386597764927 i 2 二趟 1327 6597764938 三趟 132738 97764965 四趟 13273849 769765 五趟 1327384965 9776 六趟 132738496576 97 排序结束 六趟 13273849657697 k i for j i 1 j n j if L r j key L r k key k j if i k L r i L r k 与第i个记录交换 i 6 voidSelectSort SqList L 对顺序表L作简单选择排序 SelectSort i 3 i 4 i 5 比较次数 n 1 n 2 n 6 比较次数 移动次数 正序 最小值为0 最大值为3 n 1 前n 1个为正序 第n个记录的关键字最小 时间复杂度 O n2 空间复杂度 O 1 稳定 kjdown 堆排序 堆排序就是直接选择排序算法的改进算法 堆的定义 n个元素的序列 k1 k2 kn 当且仅当满足下列关系时 称之为堆 或 i 1 2 n 2 ki k2iki k2i 1 ki k2iki k2i 1 小顶堆 大顶堆 小根堆 正堆 大根堆 逆堆 可将堆序列看成完全二叉树 则 k2i是ki的左孩子 k2i 1是ki的右孩子 所有非终端结点的值均不大 小 于其左右孩子结点的值堆顶元素必为序列中n个元素的最小值或最大值 14 32 29 87 48 34 57 93 93 48 87 29 32 57 34 14 14 6 29 87 48 10 57 93 堆排序 将无序序列建成一个堆 得到关键字最小 大 的记录 输出堆顶的最小 大 值后 将剩余的n 1个元素重又建成一个堆 则可得到n 1个元素的次小值 如此重复执行 直到堆中只有一个记录为止 每个记录出堆的顺序就是一个有序序列 这个过程叫堆排序 堆排序大体分三步处理 第一步建立堆结构 先取i n 2 i是第n个结点的双亲的编号 将以i结点 第一个非终端结点 为根的子树调整为堆 然后令i i 1 再将以i结点为根的子树调整成为堆 直到i 1为止 初建堆完成 第二步输出堆顶元素 首先输出堆顶元素第三步堆顶元素并入有序区 因此 实现堆排序需解决两个问题 1 如何将n个元素的序列按关键码建成堆 2 输出堆顶元素后 调整剩余元素成为一个新堆 如何 建堆 两个问题 如何 筛选 完全二叉树 调整为堆 81 73 64 27 98 12 第一个问题解决方法 筛选 建堆是一个从下往上 从右往左进行 筛选 的过程 例 排序之前的关键字序列为 调整为大顶堆 40 55 49 36 12 36 73 49 98 81 98 49 40 现在 左 右子树都已经调整为堆 最后只要调整根结点 使整个二叉树是个 堆 即可 81 73 55 从一个无序序列建堆的过程就是一个反复筛选的过程 例如 给定排序码25 56 49 78 11 65 41 36 建立初始堆的过程 建初始堆的方法方法 从无序序列的第 n 2 个元素 即此无序序列对应的完全二叉树的最后一个非终端结点 起 至第一个元素止 进行反复筛选 建成的大根堆 所以 第二个问题 实际上还是要归结第一个问题 堆排序的实现其实是一个递归的过程 例 输出小顶堆输出堆顶元素之后 以当前堆中最后一个元素替代之 然后将根结点值与左 右子树的根结点值进行比较 并与其中小者进行交换 重复上述操作 直至叶子结点 将得到新堆 称这个从堆顶至叶子的调整过程为 筛选 97 97 27 97 49 97 38 97 97 49 65 65 49 76 49 76 97 97 65 76 27 65 49 38 49 97 13 76 对深度为k的堆 筛选 所需进行的关键字比较的次数至多为2 k 1 voidHeapSort HeapType H 对顺序表H进行堆排序 HeapSort for i H length 2 i 0 i HeapAdjust H r i H length 建大顶堆 for i H length i 1 i H r 1 H r i 将堆顶记录和当前未经排序子序列 H r 1 i 中最后一个记录相互交换HeapAdjust H r 1 i 1 对H r 1 进行筛选 定义堆类型为 typedefSqListHeapType 堆用顺序表表示 堆排序的时间复杂度和空间复杂度 1 对深度为k的堆 筛选 所需进行的关键字比较的次数至多为2 k 1 3 调整 堆顶 n 1次 总共进行的关键字比较的次数不超过2 log2 n 1 log2 n 2 log22 2n log2n 因此 堆排序的时间复杂度为O nlogn 与简单选择排序O n2 相比时间效率提高了很多 2 对n个关键字 建成深度为h log2n 1 的堆 所需进行的关键字比较的次数至多4n 空间复杂度 S n O 1 堆排序是一种速度快且省空间的排序方法 不稳定 目录 归并排序 归并 将两个或两个以上的有序