《算法分析与设计》实验报告 完 成 日 期 ： 20011.11.10 一、实验目的 (1) 了解分治策略算法思想 (2) 掌握快速排序、归并排序算法 (3) 了解其他分治问题典型算法 二．实验内容： (1) 编写一个简单的程序，实现归并排序。 (2) 编写一段程序，实现快速排序。 (3) 编写程序实现循环赛日程表。设有n=2k 个运动员要进行网球循环赛。现要设计一个满足以下要求的比赛日程表：（1）每个选手必须与其它n-1个选手各赛一次（2）每个选手一天只能赛一场（3）循环赛进行n-1 天 三．实验要求： （1） 写出源程序，并编译运行 （2） 详细记录程序调试及运行结果 四．算法思想分析： ①归并排序：将待排序元素分成大小大致相同的两个集合，分别把对两个子集合进行排序，最终将排序号的子集合合并成为所要求的排好序的集合 ②快速排序：通过一次排序将要排序的数据分割成独立的两部分，其中一部分的所有数据比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。 ③按照分治策略，将所有选手分为两组，n 个选手的比赛日程就可以通过为 n/2 个选手设计的比赛日程表来决定。递归的对选手进行分割，直到剩下两个选手时，比赛日程表的制定就变得异常简单。这时只要让这两个选手进行比赛就可以了 五．算法源代码： ⑴归并排序： 源代码如下： #include
using namespace std; void merge(int array[], int p, int q, int r) { int i,k; int begin1,end1,begin2,end2; int* temp = new int [r-p+1]; //申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后、//的序列 //设定两个指针，最初位置分别为两个已经排序序列的起止位置 begin1= p; end1 = q; begin2 = q+1; end2 = r; k = 0; while((begin1 <= end1)&&( begin2 <= end2)) { if(array[begin1]
