目录
实验 1《分治算法实验》
一、实验目的
二、实验内容
三、算法思想分析
分治法的思想：
适用条件：
实验中具体的分治思想：
四、实验过程分析
遇到的问题及解决
实验体会
改进空间
五、算法源代码
1、归并排序：
2、快速排序
3、循环赛日程表
实验 1《分治算法实验》
一、实验目的
- 了解分治策略算法思想
- 掌握快速排序、归并排序算法
- 了解其他分治问题典型算法
二、实验内容
- 编写一个简单的程序，实现归并排序。
- 编写一段程序，实现快速排序。
- 编写程序实现循环赛日程表。设有n=2k 个运动员要进行网球循环赛。现要设计一个满足以下要求的比赛日程表：
- 每个选手必须与其它 n-1 个选手各赛一次
- 每个选手一天只能赛一场
- 循环赛进行 n-1 天
三、算法思想分析
分治法的思想：
分而治之，关键在于将大问题分割成若干子问题（最好使子问题的规模大致相同），子问题相互独立且与原有问题相同【分】；递归求解出子问题后自底向上合并解，求出原问题的解【治】
适用条件：
- 问题规模缩小到一定程度时容易解决；
- 问题具有最优子结构性质，即原问题的最优解包含子问题的最优解；
- 分解出的子问题是相互独立的，即子问题之间不包含公共子问题；
- 分解出的子问题的解可以合并为原问题的解。
实验中具体的分治思想：
- 归并排序：先将待排序元素分为两个大小大致相同的子集合，分别对每个集合递归调用归并排序函数，然后将排好序的子集合合并为所要求的排好序的集合；
- 快速排序：先确定好基准点（可以通过产生一个随机数来获取），重新划分区间，将比他大的数放到右边，小于或等于的数放到左边（不稳定的排序），递归处理左右两段，直到区间只有一个数（在递归的过程中各个元素已经处于正确位置上，不需要再合并）；（挖坑填数+分治）
- 循环赛日程表：每个选手与其他选手各赛一次（有对称性，甲与乙比即为乙与甲比），共需赛n*（n-1）场【注意：这个对称规律需要将比赛的选手本人也放进矩阵中，而不是只存他每天的对手！！即不能用第i行表示第i+1个选手，而是要将i+1存在第i行的首元素位置，这样才是一个n*n的矩阵，才有对称一说】。这里的分治即考虑到对角分布特殊——对称，将矩阵不断一分为四（递归），直到矩阵成为一个2*2的矩阵，再利用对角对称，将对角复制赋值，最后合并得到结果。
四、实验过程分析
-
遇到的问题及解决
- 在归并排序中我又一次被边界条件搞糊涂了，其实之前在数据结构的实验中已经写过一次归并了，当时是在二分查找的时候研究了很久边界条件，什么左闭右开区间、左闭右闭区间到底有什么区别，有哪些要注意的点。然后这次写归并的时候又搞糊涂了，为什么一下子是小于，一下又是小于等于。后来搜了好久，也思考了很久，归并与二分查找不同，二分查找可以左闭右开，它的左闭右开是不查找右边界的元素，但是排序的话每一个元素都要排，所以其实一般都是闭区间里排序。归并的话就是分成两个区间，两个区间都成为有序区间后再合并。至于小于还是小于等于其实是决定了这个排序是稳定还是不稳定。
- for循环中注意如果是小于则是用right-left+1，如果是小于等于则是用right-left。其实这些细节以前都已经踩过坑注意过了，但是好久没写这种代码了，又忘了这些该注意的细节，所以说各种算法的代码还是要经常练，代码熟练度不是说说而已，要多练。
- 快排与并归不同，并归是分成大小大致相同的两部分，分别排，而快排是以找出的基准点正确的排序位置，以它的位置为基准，左右两边再分别排序，而不是平均分成两部分，这也是为什么快排的最好情况和最坏情况差距很大的原因。
- 循环赛中犯了个细节错误，我想用制表符将各个数据隔开，结果写成了
System.out.print(table[i][j] + ' ');//Java中与字符串拼接才能成为字符串，这里误写成了单引号，表示字符，所以此处执行了加法，将制表符对应的ASCII码与table的值加起来后输出了
- 循环赛中根据对称性进行复制时应该以矩阵大小（length）为基础进行复制，由于刚开始是以一个4*4的矩阵为单位，所以一直没有注意到这个问题，后来我输入k=3时数组越界了，找了好久才发现这个问题，再复制时下标应该是以已知矩阵的大小为基础来加减，而不是仅仅以已知矩阵的元素下标，并且在将左下矩阵复制到右上时，左下矩阵的length应该是last – mid，而不是last – mid – 1！！！
-
实验体会
本次实验中有许多与边界有关的问题需要注意，其实不止本次实验，在每一次的编程中都是如此：用到数组就要注意数组是否越界；用到for循环就要注意循环的判断条件是否正确，循环是否执行了预期执行次数；用到while循环就要注意退出循环的条件何时能满足，什么情况下会退出，会不会造成死循环等等。这些都是有一定编程积累后就明白自己该注意哪些地方，除此之外，在与算法相关的边界条件就更加要谨慎处理了，而且犯错是在所难免的，重要的是我们要学会在犯错后通过调试找出问题所在，解决问题并引以为戒，在日后的学习工作中提醒自己注意不要再犯。本次实验中我就是通过逐步调试慢慢找到了循环赛排序问题所在，并通过自己画图找出下标应该怎么变化。虽然以后可能还会犯此类错误，但只要掌握了方法，就能将其改正。所以学会调试对我们来说是非常重要的。
-
改进空间
- 由于本次实验主要是学习分治思想，学会实现几种排序算法，所以对于程序的健壮性没有特别在意，可以将只对整数排序改成对浮点数排序。
- 对于用户的输入没有判断是否合法，只是在让用户输入时通过提示信息规范用户输入，之后就默认用户输入正确且合法了，其实可以加入一些错误判断及处理信息，但那不是本次实验的重点，所以也没有写这些，主要是要理清各种算法的思想，感觉多考虑这些，代码一长，那些算法的重点逻辑就乱了，所以我将主要注意力集中在其实现思想上，没有考虑这些。
- 其实使用递归效率相对来说是比较低的，因为用到了栈，额外开销比较大，可以考虑看能不能找出其递推公式，将递归改成递推或者考虑使用迭代，但是分治的精髓就在于将原问题分解成若干规模更小的子问题，且子问题与原问题同构，用递归更能显示出这个特点，所以就没有考虑进一步改进，将递归改为递推等来提升效率了。
五、算法源代码
1、归并排序：
import java.util.Scanner;
public class MergeSort {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int n;//待排序序列有多少个元素
System.out.print("请输入待排序序列元素个数：");
n = input.nextInt();
System.out.println("请输入待排序序列(要求为整数)：");
int[] data = new int[n];
for(int i = 0; i < n;i++){
data[i] = input.nextInt();
}
mergeSort(data, 0, n-1);//[0,n - 1]
System.out.println("归并排序的结果为：");
for(int i = 0; i < n; i++){
System.out.print(data[i]+" ");
}
}
public static void mergeSort(int[] data, int left, int right){
if(left < right){//相等时区间只有一个元素，已经有序，不用再排
int mid = (left + right) / 2;
mergeSort(data, left, mid);//将[left, mid]的元素排序
mergeSort(data, mid + 1, right);//[mid + 1, right]
merge(data, left, mid, right);//将上述两个区间合并
}
}
public static void merge(int[] data, int left, int mid, int right){
int[] temp = new int[right - left + 1];//申请空间用来存放合并后的序列
//第一个有序数组是从left到mid---[left, mid]
int begin1 = left;
int end1 = mid;
//第二个有序数组是从mid+1到right---[mid + 1, right]
int begin2 = mid + 1;
int end2 = right;
int i = 0;
while((begin1 <= end1)&&(begin2 <= end2)){
if(data[begin1] <= data[begin2]){//若判断条件为<, 则是一个不稳定的排序，因为相等时将后面的排前面了
temp[i] = data[begin1];
i++;
begin1++;
}else {
temp[i] = data[begin2];
i++;
begin2++;
}
}
//若第一个数组还有剩余
while(begin1 <= end1){
temp[i] = data[begin1];
i++;
begin1++;
}
//若第二个还有剩余
while(begin2 <= end2){
temp[i] = data[begin2];
i++;
begin2++;
}
for(i = 0; i < right - left + 1; i++){//注意要+1
data[left + i] = temp[i];
}
}
}
2、快速排序
import java.util.Scanner;
public class QuickSort {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int n;//待排序序列有多少个元素
System.out.print("(quicksort)
请输入待排序序列元素个数：");
n = input.nextInt();
System.out.println("请输入待排序序列(要求为整数)：");
int[] data = new int[n];
for(int i = 0; i < n;i++){
data[i] = input.nextInt();
}
quickSort(data, 0, n-1);//[0,n - 1]
System.out.println("归并排序的结果为：");
for(int i = 0; i < n; i++){
System.out.print(data[i]+" ");
}
}
public static void quickSort(int[] data, int left, int right){
if(left < right){
int index = partition(data, left, right);//index处元素已经正确排序，接下来只需要将其左右分别进行排序
quickSort(data, left, index - 1);
quickSort(data, index + 1, right);
}
}
public static int partition(int[] data, int left, int right){
int pivotIndex = (int)(Math.random()*right) + 1;
int pivot = data[pivotIndex];//随机产生一个下标作为基准,并将基准与第一个元素交换
data[pivotIndex] = data[left];
data[left] = pivot;
while(left < right){
while (data[right] > pivot && right > left){
right--;
}
//退出上面的while循环时有data[right] <= pivot
if(left < right){
data[left] = data[right];
}
while (data[left] <= pivot && left < right) {
left++;
}
//退出上面的while循环时有left > pivot
if(left < right){
data[right] = data[left];
}
}
//退出时有left = right，这个位置就是pivot排好序时应该排的位置
data[left] = pivot;
return left;
}
}
3、循环赛日程表
import java.util.Scanner;
public class RoundRobinTable {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
System.out.print("循环赛日程表：总运动员数量为2的k次方
请输入k的值(要求为整数)：");
int k = input.nextInt();
int n = (int)Math.pow(2, k);
int[][] table = new int[n][n];//日程表为n行n-1列，每一列表示一天，每一行表示每个运动员每天的对手
for(int i = 0; i < n; i++){
table[i][0] = i + 1;//将每一行的第一个元素赋值，从1-n，表示是第几位选手
}
roundRobin(table, 0, n - 1);
for(int i = 0; i < n; i++){
for (int j = 0; j < n; j++){
System.out.print(table[i][j] + " ");
}
System.out.print('
');
}
}
public static void roundRobin(int[][] table, int first, int last){
//first：表中第一个选手的编号，last：表中最后一个选手的编号
if(last - first == 1){//当一共只有两个选手时直接通过对称就能得到结果
table[first][1] = table[last][0];
table[last][1] = table[first][0];
return;
}
int mid = (first + last) / 2;
roundRobin(table, first, mid);//左上角
roundRobin(table, mid + 1, last);//左下角
//右上和右下不用再求了，由对称性可以直接复制
//右下 = 左上
int length = mid + 1 - first;
for(int i = first; i < mid + 1 ; i++){
for(int j = 0; j < mid + 1 - first; j++){
table[length + i][length + j] = table[i][j];
}
}
//右上 = 左下
length = last - mid;
for(int i = mid + 1; i < last + 1; i++){
for(int j = 0; j < mid + 1 - first; j++){
table[i - length][length + j] = table[i][j];
}
}
}
}