文档介绍：本科实验报告
课程名称:
算法设计与分析B
实验项目:
分治法合并排序问题、贪心法
作业调度问题、动态规划法多段 图问题、回溯法求 N皇后问题
实验地点:
行知楼C124
专业班级:
软件工程 学号:
学生姓名:
指导教师：
王幸民
2015年 04月 11日
实验一分治法合并排序
一实验目的
.掌握合并排序的基本思想
.掌握合并排序的实现方法
.学会分析算法的时间复杂度
.学会用分治法解决实际问题
二实验内容
随机产生一个整型数组， 然后用合并排序将该数组做升序排列， 要求输出排序前和排序
后的数组。
三实验环境
程序设计语言：C++
编程工具：Microsoft Visual Studio 2013
四算法描述及程序代码
#include ""
#include <iostream> using namespace std;
const int n=10;
//数组大小]
const int max = 100;
//定义一个值设为无穷大
int Arr1[n / 2 + 1], Arr2[n / 2 + 1];
MergeSort(Arr, 0, n - 1);
cout << "\n归并排序后的结果为："<< endl;
for ( int i = 0; i < n; i++)
cout<< Arr[i]<< "";
cout << "\n";
return 0;
}
void MergeSort( int *Ap, int p, int r);
int _tmain (int argc , _TCHAR argv[])
{
int Arr[n];
cout << "请输入10个任意数字 (<100) : " << endl;
for ( int i = 0; i < n; i++)
cin >> Arr[i];
//调用归并排序函数
cout << "归并排序前的数组为："<< endl;
for ( int i = 0; i < n; i++)
void Merge(int * Ap, int p, int q, int r){ int i=0, j=0;
int n1 = q - p + 1;
int n2 = r - q;
for ( int i = 0; i < n1; i++)
Arr1[i] = Ap[ p + i];
for ( int i = 0; i < n1; i++)
Arr2[i] = Ap[q + i+1];
Arr1[n1] = max;
//设立一个标签值为无穷大
Arr2[n2] = max;
while (p<=r){
//合并两个小的有序数列
if ((Arr1[i] <
cout << Arr[i] <<
Arr2[j])&&Arr1[i]<100)
if ( p < r){
//递归调用本身
q = ( p + r) / 2;
MergeSort( Ap, p, q);
MergeSort( Ap,q+1, r);