数据分析与算法设计-习题课20161101

数据分析与算法设计 习题课数据分析与算法设计 习题课 第一次第一次 第四次作业第四次作业 信电学院信电学院 王梁昊王梁昊 wanglianghao645840 第一次作业第一次作业 习题习题1 2 第第1题题 习题习题1 3 第第4题题 习题习题1 3 第第5题题 习题习题2 1 第第10题题 习题习题2 2 第第5题题 习题习题2 5 第第8题题 习题习题1 2 第第1题题 习题习题1 3 第第4题题 1736年29岁的欧拉向圣彼得堡科学院递交 了 哥尼斯堡的七座桥 的论文 在解答问 题的同时 开创了数学的一个新的分支 图论与几何拓扑 也由此展开了数学史上的 新历程 连通图可以一笔画 的充要条件是 奇 点的数目不是0个 就是2个 要想一笔画成 必须中间点均是偶点 也就是有来路必有另一条去路 奇点 只可能在两端 因此任何图能一笔画成 奇点要么没有要么在两端 习题习题1 3 第第5题题 习题习题2 1 第第10题题 习题习题2 2 第第5题题 习题习题2 5 第第8题题 没有必要特意使用一个数组来存储数列中前 面的元素 为了完成该任务 只需要存储两 个元素就足够了 第二次作业第二次作业 习题习题3 1 第第12题题b 习题习题4 1 第第8题题 习题习题4 1 第第12题题a b 希尔排序 希尔排序 习题习题5 2 第第4题题 习题习题5 2 第第9题题 习题习题3 1 第第12题题b 习题习题4 1 第第8题题 哨兵 限位器 习题习题4 1 第第12题题a b 希尔排序 希尔排序 希尔排序希尔排序 希尔排序是希尔排序是1959 年由年由D L Shell 提出来的 相对提出来的 相对 直接排序有较大的改进 希尔排序又叫缩小增量直接排序有较大的改进 希尔排序又叫缩小增量 排序排序 基本思想基本思想 先将整个待排序的记录序列分割成为若干子序列先将整个待排序的记录序列分割成为若干子序列 分别进行直接插入排序 待整个序列中的记录 分别进行直接插入排序 待整个序列中的记录 基本有序 时 再对全体记录进行依次直接插入基本有序 时 再对全体记录进行依次直接插入 排序 排序 希尔排序希尔排序 操作方法操作方法 选择一个增量序列d1 d2 dm 其中dki dkj dm 1 按增量序列个数m 对序列进行m趟排序 每趟排序 根据对应的增量dk 将待排序列分割成若干 子序列 分别对各子表进行直接插入排序 仅增量因 子为1时 整个序列作为一个表来处理 表长度即为整 个序列的长度 38 例 例 关键字序列关键字序列 T 49 38 65 97 76 13 27 49 55 04 请写出希尔排序的具体实现过程 请写出希尔排序的具体实现过程 0 1 2 3 4 5 6 7 8 9 10 49 38 65 97 76 13 27 49 55 04 初态 初态 第第1趟趟 dk 5 第第2趟趟 dk 3 第第3趟趟 dk 1 49 13 13 49 38 27 65 49 97 55 76 04 27 38 65 49 97 55 13 55 76 04 55 13 27 04 27 04 49 49 49 49 76 38 76 65 65 97 97 55 13 27 04 49 49 38 76 65 97 13 27 04 49 76 97 算法分析 算法分析 开始时开始时d dk k的值较大 子序列中的对象较少 排序速的值较大 子序列中的对象较少 排序速 度较快 随着排序进展 度较快 随着排序进展 d dk k 值逐渐变小 子序列中对象 值逐渐变小 子序列中对象 个数逐渐变多 由于前面工作的基础 大多数对象已基个数逐渐变多 由于前面工作的基础 大多数对象已基 本有序 所以排序速度仍然很快 可以看出 本有序 所以排序速度仍然很快 可以看出 49 49 排序后排序后 出现在出现在4949的前面 故希尔算法是不稳定的 的前面 故希尔算法是不稳定的 r i 希尔排序示例希尔排序示例 希尔排序分析希尔排序分析 时间效率时间效率 希尔排序时效分析很难 关键码的比较次数与记录移 动次数依赖于增量因子序列d的选取 特定情况下可以 准确估算出关键码的比较次数和记录的移动次数 目前还没有人给出选取最好的增量因子序列的方法 增量因子序列可以有各种取法 有取奇数的 也有取 质数的 但需要注意 增量因子中除1外没有公因子 且最后一个增量因子必须为1 空间效率 空间效率 O 1 稳定性 不稳定稳定性 不稳定 习题习题5 2 第第4题题 习题习题5 2 第第9题题 荷兰国旗呈长方形 长宽比为3 2 自上而 下由红 白 蓝三个平行相等的横长方形相 连而成 蓝色表示国家面临海洋 象征人民 的幸福 白色象征自由 平等 民主 还代 表人民纯朴的性格特征 红色代表革命胜利 在位 原地 算法 课本P16 第三次作业第三次作业 习题习题3 2 第第6题题 习题习题4 4 第第8题题 习题习题4 5 第第6题 参考题 参考 2 2 6 习题习题5 5 第第7题题 习题习题7 2 第第2题题 习题习题7 2 第第4题题 习题习题3 2 第第6题题 习题习题4 4 第第8题题 习题习题4 5 第第6题题 习题习题5 5 第第7题题 习题习题7 2 第第2题题 习题习题7 2 第第4题题 第四次作业第四次作业 习题习题5 3 第第5题题 习题习题6 3