(
课件网) 排序算法———归并排序 信息学奥林匹克竞赛（入门）【高中】 排序算法———归并排序 Content 归并排序算法精讲 经典例题讲解 排序算法———归并排序 -Content 排序算法———归并排序 归并排序算法精讲 排序算法———归并排序 排序算法———归并排序 排序算法———归并排序 -归并排序算法精讲 Example 1 杠铃增重问题 每位参赛运动员向组委会提交排好序的三次试举重量 杠铃增重顺序： 问题：组委会如何根据试举重量安排杠铃增重顺序？ 排序算法———归并排序 -Example 1 归并排序算法精讲 Example 1 杠铃增重问题 选择排序 从待排序元素中迭代选出最小值并排序 比较次数：66次 选择排序：依次将每个元素插入到已排列序列之中 比较次数：55次 问题：是否还有更高效的算法？ 排序算法———归并排序 -Example 1 归并排序算法精讲 Example 1 杠铃增重问题 问题特点：局部有序 快速合并：比较两有序数组当前最小元素，将较小者逐一合入新数组 排序算法———归并排序 -Example 1 归并排序算法精讲 Example 1 杠铃增重问题 问题特点：局部有序 快速合并：比较两有序数组当前最小元素，将较小者逐一合入新数组 后续策略：逐一合并，比较27次 排序算法———归并排序 -Example 1 归并排序算法精讲 Example 1 杠铃增重问题 问题特点：局部有序 快速合并：比较两有序数组当前最小元素，将较小者逐一合入新数组 后续策略： 逐一合并，比较27次 两两合并：比较24次 策略名称 4位选手 8位选手 16位选手 逐一合并 27次 105次 405次 两两合并 24次 72次 192次 求解杠铃增重问题的两两合并策略对排序问题有何启发？ 排序算法———归并排序 -Example 1 归并排序算法精讲 归并排序 定义：归并排序是建立在归并操作上的一种有效，稳定的排序算法，该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列。 历史：1945年，冯 诺依曼提出归并排序。 算法流程： 将数组排序问题分解为和排序问题 递归解决子问题得到两个有序的子数组 将两个有序子数组合并为一个有序数组 排序算法———归并排序 归并排序算法精讲 -归并排序 归并排序 分解原问题 解决子问题 合并问题解 原问题分解为多个子问题 递归求解各个子问题 将结果合并为原问题解 归并排序： 分解数组， 递归求解， 合并排序 排序算法———归并排序 归并排序算法精讲 -归并排序 归并排序 程序复杂度： 分析方法：递归树法 框架： 排序算法———归并排序 归并排序算法精讲 -归并排序 Example 2 对以下数组进行排列： 下面我们运用归并排序算法对此数组进行排序 i 0 1 2 3 4 a[i] 19 15 37 12 25 排序算法———归并排序 归并排序算法精讲 -Example 2 第一步：分解 首先将数组分解成两部分，即19、15、37为一组，12、25为一组，为了区分，我们起个名字叫“第一层”，如下： 19 15 37 12 25 排序算法———归并排序 归并排序算法精讲 -Example 2 第二步：分解 继续分解，19、15为一组，37为一组，12为一组，25为一组，这四组为“第二层”，如下： 19 15 25 37 12 排序算法———归并排序 归并排序算法精讲 -Example 2 第三步：分解 继续分解，此时只剩下19、15这一组可以分解，分解成19、15，这两组为“第三层”，如下： 15 19 排序算法———归并排序 归并排序算法精讲 -Example 2 第四步：归并 由于所有组都已经分解成只有1个元素，开始进行归并，从“高层”开始归并，即先归并“第三层”，比较“第三层”两组元素，19 < 15，因此将15排在19前面，由于已经没有元素，结束此次归并，如下： 19 15 排序算法———归并排序 归并排序算法精讲 -Example 2 第五步： ... ...
