算法设计与分析(第2版微课版高等学校数据结构课程系列教材)

作者简介

李春葆，武汉大学计算机学院教授。主要研究方向为数据挖掘和算法设计，先后主持和参加多个大型研究项目。主要为本科生讲授数据结构(15年以上)和软件工程等课程，为研究生讲授软件开发新技术、数据仓库与数据挖掘等课程，并出版十多部精品著作。

内容简介

第3章分治法 分治法是使用最广泛的算法设计方法之一。其基本策略是采用递归思想把大问题分解成一些小问题，然后由小问题的解方便地构造出大问题的解。本章介绍分治法求解问题的一般方法，并给出一些用分治法求解的经典示例。 3.1分治法概述 3.1.1分治法的设计思想 对于一个规模为n的问题，若该问题可以容易地解决(例如规模n较小)则直接解决，否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解，这种算法设计策略叫分治法。 如果原问题可分割成k(1 void disp(int a［］,int n)//输出a中的所有元素 {int i; for (i=0;ii && a［j］>=tmp) j--; 　　//从右向左扫描,找第1个关键字小于tmp的a［j］ a［i］=a［j］; 　　//将a［j］前移到a［i］的位置 while (i2，即归并操作在相邻的多个有序子表中进行，则叫多路归并排序。这里仅讨论二路归并排序算法，二路归并排序算法主要有两种，下面一一讨论。 \\\"难度适中，强调算法设计和动手能力培养 注重实验，提供大量的上机实验题和在线编程题 案例来源于著名IT企业面试笔试题和ACM竞赛题 教学资源丰富，每个知识点都配套了视频讲解\\\"