《计算机应用基础课件》1.6排序VIP

第1章数据结构 主要内容1 1基本数据结构与算法1 2线性表1 3栈和队列1 4树和二叉树1 5查找1 6排序 姓名学号成绩班级李红976105995机97 6 10 65 865 1 6排序 排序又称分类 是计算机程序设计中一个重要运算 它的功能是将一组任意序列的数据元素 进行按关键字由大到小的顺序 降序 排列或按由小到大的顺序 升序 排列 排序的对象 这些数据元素可以是数值型 也可以为字符型 若为数值型 则按数值大小排列 若为字符型 则按其ASCII码的顺序排列 排序的依据 在实际应用中 参加排序的数据元素有时不是单个数据项 而是由多个数据项组成的记录 此时排序应按照关键字的大小进行 所谓关键字是指记录中的某个数据项 用它可以标识一个记录 若此关键字可以唯一地标识一个记录 则称此关键字为主关键字 反之 把用以识别若干记录的关键字称为次关键字 排序的稳定性 在待排序的记录中 若存在多个关键在相同的记录 经过排序后 这些具有相同关键在的记录之间的相对次序发生变化 则称这种排序方法是稳定的 否则 是不稳定的 排序的分类 内部排序与外部排序内部排序 整个排序过程完全在内存中进行 外部排序 由于待排序记录数据量太大 内存无法容纳全部数据 排序需要借助外部存储设备才能完成 排序算法评价 算法执行时间 最好 最差及平均情况 需要附加空间大小 1 6排序 插入排序的基本思想 1 6 2插入排序 插入排序三种方法1 直接排序 认可第1个记录已排好序 然后将第2个到第n个记录依次插入到前面已排好序的记录组成的文件中 2 折半插入排序 折半插入排序在寻找插入位置时 不是逐个比较而是利用折半查找的原理寻找插入位置 待排序元素越多 改进效果越明显 3 希尔排序 将整个无序序列分割成若干个子序列分别进行直接插入排序 将待排序文件中的记录 逐个按其排序码值的大小插入到已排好序的若干个记录组成的文件中的适当位置 保持新文件有序 1 直接插入排序 思路 认可第1个记录已排好序 然后将第2个到第n个记录依次插入到前面已排好序的记录组成的文件中 具体过程 第i个记录Ri插入到前面i 1个已排好序的记录中 将Ri的排序码与前面已排好序的排序码从右向左依次比较 找到Ri应插入的位置 将该位置以后直到Ri 1各记录顺序后移 空出位置插入Ri 1 6 2插入排序 直接插入排序 次数ir 0 r 1 r 2 r 3 r 4 r 5 r 6 r 7 r 8 49 39669676113750 3949 669676113750 i 2 39 394966 9676113750 i 3 66 39496696 76113750 i 4 96 3949667696 113750 i 5 76 113949667696 3750 i 6 11 11373949667696 50 i 7 37 1137394950667696 i 8 50 对于有n个数据元素的待排序列 插入操作要进行n 1次 对N个整数进行升序排序 for i 1 i 0 k 寻找插入位置if a i a k break 插入到第k个位置的后面temp a i for j i 1 j k j 向后移动a j 1 a j a j 1 temp 改进前面的算法 for i 1 i 0 temp a j 若降序排序 则 1 直接插入排序 时效分析 最好情况 初始排序码已经有序 共比较n 1次 移动0次 最坏情况 待排序序列完全逆序 比较和移动均为n n 1 2次 平均情况 比较和移动次数均约为n2 4 时间复杂度为O n2 1 6 2插入排序 该算法适合于n较小的情况 时间复杂度为O n2 2 折半插入排序折半插入排序在寻找插入位置时 不是逐个比较而是利用折半查找的原理寻找插入位置 待排序元素越多 改进效果越明显 折半插入排序减少了关键字的比较次数 但记录的移动次数不变 其时间复杂度与直接插入排序相同为O n2 1 6 2插入排序 3 希尔排序 基本思想 将整个无序序列分割成若干个子序列分别进行直接插入排序 待整个序列中的记录 基本有序 时 再对全体记录进行一次直接插入排序 子序列分割 选定两个元素之间距离h 将所有间隔为h的元素分成一组 将相隔某个增量h的元素构成一个子系列 具体实现 1 选择一个增量序列t1 t2 tk 其中ti tj tk 1 2 按增量序列个数k 对序列进行k趟排序 3 每趟排序 根据对应的增量ti 将序列分割成若干长度为m的子序列 分别对各子表直接插入排序 增量ti逐次减小 tk 1时 再对全部元素进行一次直接插入排序即可完成 1 6 2插入排序 举例 有一个含有14个数的序列 使用希而排序进行升序排序 39 80 76 41 13 29 50 78 30 11 100 7 41 86 取增量 5 3 1 h 5 3980764113295078301110074186 R1 R6 R11 3929100 R2 R7 R12 80507 R3 R8 R13 767841 R4 R9 R14 413086 R5 R10 1311 则子序列 39 29 100 80 50 7 76 78 41 41 30 86 13 11 R1 R2 R3 R4 R5 R6 R7 R8 R9 R10R11 R12 R13 R14 h 5 3980764113295078301110074186 子序列 39 29 100 80 50 7 76 78 41 41 30 86 13 11 R1 R2 R3 R4 R5 R6 R7 R8 R9 R10R11 R12 R13 R14 2939100 75080 417678 304186 1113 因此第一趟排序结果如下 2974130113950764113100807886 对每个序列进行直接插入排序 h 3 2974130113950764113100807886 2930501378 7117610086 41394180 分别对以上3个子序列 即 29 30 50 13 78 7 11 76 100 86 41 39 41 80 进行直接插入排序 1373929114130764150868078100 R1 R4 R7 R10 R13 R2 R5 R8 R11 R14 R3 R6 R9 R12 R1R2R3R4R5R6R7R8R9R10R11R12R13R14 1329305078 7117686100 39414180 第二趟最终结果 第一趟排序结果 1373929114130764150868078100 h 1序列基本有序 对其进行直接插入排序 第三趟最终结果 7111329303941415076788086100 第二趟最终结果 3 希尔排序 特点 每一遍以不同间隔距离插入排序 h较大时移动数据元素是跳跃式进行 子序列每一次比较可能移去多个逆序 直接插入排序每次比较只能移去一个 效率较高 最后一次排序 h 1 时 已基本有序 不需要多少移动 故其时间复杂度较直接插入排序低 数学难题 如何选取增量序列才能有最好的排序效果 至今未完整解决 但注意 增量序列中除1外没有公因子 且最后一个增量序列必须为1 时效分析 很难 比较次数与移动次数依赖于增量序列的选取 特定情况下可以估计 1 6 2插入排序 对待排序记录两两比较排序码 不满足排序顺序则交换 直到任何两个记录排序码满足排序要求 基本思路 交换排序种类 冒泡排序快速排序 1 6 3交换排序 1 冒泡排序基本思想 通过相邻元素的交换 逐步将线性表变成有序 基本过程 第一趟冒泡排序 首先第一个元素与第二个元素比较 逆序则交换 然后第二个元素与第三个元素比较 直到第n 1个元素与第n个元素比较为止 结果 关键字 最大的元素放在最后位置 第二趟冒泡排序 对前面n 1个元素进行相同操作 结果次大元素放在n 1位置上 第i趟冒泡排序 对前面n i 1个元素进行相同操作 结果 n i 1 中最大元素放在 n i 1 位置上 趟数 最多n 1 结束条件 在某一趟排序中没有进行交换元素操作 1 6 3交换排序 38 49 76 97 13 97 27 97 30 97 13 76 76 76 27 30 13 65 27 65 30 65 13 13 49 49 30 49 27 38 27 38 30 38 思想 小的浮起 大的沉底 举例 将数列 8 6 5 7 1 升序排序 初始86571 第一趟65718 第二趟56178 第三趟51678 第四趟15678 初始已排好序 正序最好 则只需进行一趟排序 比较次数n 1 移动次数为0 逆序 最坏 则需进行n 1趟排序 比较次数为 1 2 3 n 1 n n 1 2 是稳定的排序 时间复杂度为O n2 空间复杂度是O 1 时效分析 程序代码 defineN5 intgrade N temp for i 0 igrade j 1 temp grade j 1 grade j 1 grade j grade j temp 读入5个值保存在数组中 16 71 46 90 85 temp 46 temp 71 temp 16 16 71 46 90 85 i 0第1趟 j 0从头开始比较 j 4 条件不成立 j 1 j 4 条件成立 90 46 j 2 j 4 条件成立 90 71 j 3 j 4 90 16 j 4 内层循环终止 90 即 i 0第1趟时grade 0 和grade 1 比较grade 1 和grade 2 比较grade 2 和grade 3 比较grade 3 和grade 4 比较最大值放到grade 4 中 defineN5 for i 0 igrade j 1 temp grade j 1 grade j 1 grade j grade j temp 即 i 0第1趟时内存循环for j 0 j N 1 i j 变量j是从0到3的 16 71 46 90 85 i 1第2趟 j 0从头开始比较 90 46 90 71 90 16 90 defineN5 for i 0 igrade j 1 temp grade j 1 grade j 1 grade j grade j temp 内存循环for j 0 j N 1 i j 中j的取值从0到2grade 0 和grade 1 比较grade 1 和grade 2 比较grade 2 和grade 3 比较找出次大值放到grade 3 中 16 71 46 90 85 i 1第2趟 90 46 90 71 90 16 90 85 46 85 71 85 16 85 defineN5 for i 0 igrade j 1 temp grade j 1 grade j 1 grade j grade j temp 16 71 46 85 i 2第3趟 90 46 90 71 90 16 90 85 46 85 71 85 16 85 71 71 16 defineN5 for i 0 igrade j 1 temp grade j 1 grade j 1 grade j grade j temp 16 71 46 85 i 3第4趟 90 46 90 71 90 16 90 85 46 85 71 85 16 85 71 71 16 defineN5 for i 0 igrade j 1 temp grade j 1 grade j 1 grade j grade j temp 46 16 46 2 快速排序 基本思想 通过一趟排序将待排记录分割成独立两部分 其中一部分记录的关键字均比另一部分记录的关键字小 再对前 后两部分待排记录重复上述过程 直到所有子表表长不超过1为止 优点 通过两个不相邻元素交换 可以一次交换消除多个逆序 加快排序速度 4939669676112750 273911 49 76966650 273949 5066 7696 1 6 3交换排序 2 快速排序 过程 首先任选一个记录K 通常选第一个记录 作为枢轴 支点 附设两个指针i和j分别指向第一个记录和最后一个记录 1 指针j向前搜索逐个记录与K比较 直到发现小于K的记录为止 将其与枢轴记录互相交换 2 指针i向后搜索逐个记录与K比较 直到发现大于K的记录为止 将其与枢轴记录互相交换 3 重复 1 2 直至i j为止 完成一趟排序 完成一次分割 以K为分界线 对前后两个子表按上述原则再分割 直到所有子表的表长不超过1 为空 为止 1 6 3交换排序 4939669676112750 第1次交换 向前 小的与枢轴交换 即27与49交换 第2次交换 向后 大的与枢轴交换 即66与49换 第3次交换 11与49换 完成一趟排序 初始关键字 第4次换 96与49换 2739114976966650 举例 将 49 39 66 96 76 11 27 50 进行一趟快速排序分析 取第一个数49为枢轴 即K 49 空处是枢轴为49 4939669676112750 273911 49 76966650 一次划分之后 快速排序的全过程 初始关键字 分别进行快速排序 11 27 39 5066结束 结束结束 5066 76 96 结束 1127394950667696 有序序列 时效分析 平均时间复杂度最佳为O nlog2n 最坏情况时间效率为O n2 基本思想 每次从待排序的记录中选出关键字最小的记录 顺序存放在已排序的记录序列的后面 直到全部排完 选择排序种类 直接选择排序和堆排序 1 直接选择排序 以升序为例 首先从所有n个待排序记录中选择关键字最小的记录 与第1个记录交换 第1遍进行n 1次比较 再从剩下的n 1个记录中选出关键字最小的记录 与第2个记录交换 第2遍进行n 2次比较 重复操作进行n 1遍 直到待排序序列全部有序为止 1 6 4选择排序 1 直接选择排序 正序 移动次数为0逆序 移动次数为3 n 1 执行n n 1 2次比较 举例 将 89 21 56 48 85 16 19 47 直接选择排序 原序列8921564885161947 最后结果进行n 1 7次选择 1 6 4选择排序 时效分析 选择法排序for i 0 ia k k j if k i temp a i a i a k a k temp 例 初始 49386597761327 i 1 13 49 一趟 13 386597764927 i 2 27 38 六趟 132738496576 97 从小到大排序 2 堆排序堆定义 n个元素的序列 K1 K2 Kn 当且仅当满足下列关系时 称为堆 ki k2iki k2i 1 ki k2iki k2i 1 小根堆或 大根堆 堆结构 完全二叉树表示 将序列对应的一维数组看成一个完全二叉树 在堆中 堆顶元素必为序列中n个元素的最小值 或最大值 小根堆 大根堆 其中 i 1 2 n 2 1 6 4选择排序 首先包括n个元素的序列建堆 输出堆顶最小值 得到n个元素中最小元素 然后再对剩下n 1个元素重建堆 输出堆顶元素 得到n个元素中次小元素 反复执行 直到剩下子序列为空 便得到一个有序列 2 堆排序 排序过程 两个问题 实现堆排序需解决 1 如何将n个元素的无序序列建成一个堆 2 输出堆顶元素后 调整剩余元素成为一个新堆 输出堆顶元素后 以堆中最后一个元素代替之 此时根结点左 右子树均为堆 仅需自上而下调整即可 1 6 4选择排序 方法 将根结点与左 右子树根结点比较 若不满足堆条件 则较小值与根结点交换 顺序 从完全二叉树最后一个非终端结点 第n 2个元素 开始 直到根结点 第一个元素 为止 对每一个结点 调整建堆 举例 一个无序序列 49 39 66 96 76 11 27 50 建小根堆的过程1 从第一个非叶子结点 序号 n 2 8 2 4 即图中值为96的结点开始筛选 筛选原则是保证父结点的值要小于或等于叶子接点 第4个结点96被筛选后状态 第3个结点66被筛选后状态 目前的堆中 堆顶元素11为最小值 输出后 重新对n 1个元素重新建一个新堆 新堆中的堆顶是剩余的n 1个元素中的最小值 n个元素中的次最小值 49被筛选后建成的堆 该处理第1个结点 举例 输出堆顶元素并建新堆过程 堆 11 11与96交换后情形 输出堆顶元素之后 以堆中最后一个元素替代之 此时根结点的左 右子树均为堆 仅需自上至下进行调整即可 11 27与96交换后情形 11 调整后新堆 27为新堆中的最小值 27 输出27 用96替代 11 96与39换 11 27 96与50换 调整后新堆 27为新堆中的最小值 11 调整后新堆 39为新堆中的最小值 继续此过程 调整后新堆 39为新堆中的最小值 11 27 39 11 27 输出堆顶元素 堆顶元素和树中最后一个结点对调 重建堆 因为除了堆顶的根结点 左右子树已经是堆 自上而下进行调整即可 反复执行直到剩下子序列为空 便得到一个有序列 堆排序的时效分析 最坏情况下 时间复杂度为O nlog2n 仅需一个记录大小供交换用的辅助存储空间 适合规模较大的线性表 排序小结 查找与排序补充习题讲解 1 链表适用于 查找 A 顺序B 二分法C 顺序 也能二分法D 随机2 对长度为n的线性表进行顺序查找 在最坏情况下所需要的比较次数为 A log2nB n 2C nD n 1 05年4月 3 已知一个有序表为 13 18 24 35 47 50 62 83 90 115 134 当使用二分法查找90的元素时 查找成功的比较次数为 A 1B 2C 3D 94 在排序算法中 两两比较待排序的记录 当发现不满足顺序要求时 变更他们的相对位置 这就是 排序 A 希尔排序B 交换排序C 插入排序D 选择排序 ACBB 5 设待排序关键码序列为 33 18 9 25 67 82 53 95 12 70 要按关键码值递增的顺序排序 采取以第一个关键码为分界元