实验一 分治策略排序
一、实验目的
1）以排序问题为例，掌握分治法的基本设计策略；
2）熟练掌握合并排序算法的实现；
3）熟练掌握快速排序算法的实现；
4) 理解常见的算法经验分析方法。
二、算法思路
1. 合并排序算法思想：
分而治之(divide - conquer);每个递归过程涉及三个步骤
第一, 分解: 把待排序的 n 个元素的序列分解成两个子序列, 每个子序列包括 n/2 个元素.
第二, 治理: 对每个子序列分别调用归并排序MergeSort, 进行递归操作
第三, 合并: 合并两个排好序的子序列,生成排序结果.
最坏时间复杂度 
最好时间复杂度
空间复杂度 
2.快速排序算法思想：
通过一躺排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一不部分的所有数据都要小，然后再按次方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。假设要排序的数组是A[1]……A[N]，首先任意选取一个数据（通常选用第一个数据）作为关键数据，然后将所有比它的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一躺快速排序。一躺快速排序的算法是：
1）、设置两个变量I、J，排序开始的时候I：=1，J：=N；
2）以第一个数组元素作为关键数据，赋值给X，即X：=A[1]；
3）、从J开始向前搜索，即由后开始向前搜索（J：=J-1），找到第一个小于X的值，两者交换；
4）、从I开始向后搜索，即由前开始向后搜索（I：=I+1），找到第一个大于X的值，两者交换；
5）、重复第3、4步，直到I=J；
三、实验内容：
1. 准备实验数据
要求：编写一个函数data-generate，生成2000个在区间[1,10000]上的随机整数，并将这些数输出到外部文件data.txt中。这些数作为本算法实验的输入数据。
2. 实现合并排序算法
要求：实现mergesort算法。
输入：待排数据文件data.txt；
输出：有序数据文件resultsMS.txt（注：建议将此排好序的数据作为实验二的算法输入）；程序运行时间TimeMS。
合并排序算法（类C语言）：
/* 数组A[] 中包含待排元素；array B[] is a work array */
TopDownMergeSort(A[], B[], n)
{
TopDownSplitMerge(A, 0, n, B);
}
// iBegin is inclusive; iEnd is exclusive (即：A[iEnd]不是待排元素)
TopDownSplitMerge(A[], iBegin, iEnd, B[])
{
if(iEnd - iBegin < 2) // 如果只有1个待排元素，返回。
return;
// recursively split runs into two halves until run size == 1,
// then merge them
iMiddle = (iEnd + iBegin) / 2; // 划分
TopDownSplitMerge(A, iBegin, iMiddle, B);
TopDownSplitMerge(A, iMiddle, iEnd, B);
TopDownMerge(A, iBegin, iMiddle, iEnd, B); // 合并；元素放到数组B中。
CopyArray(B, iBegin, iEnd, A); // copy the merged runs back to A
}
// left half is A[iBegin : iMiddle-1]
// right half is A[iMiddle : iEnd-1]
TopDownMerge(A[], iBegin, iMiddle, iEnd, B[])
{
i0 = iBegin, i1 = iMiddle;
// While there are elements in the left or right runs
for (j = iBegin; j < iEnd; j++) {
// If left run head exists and is <= existing right run head.
if (i0 < iMiddle && (i1 >= iEnd || A[i0] <= A[i1])) {
B[j] = A[i0];
i0 = i0 + 1;
} else {
B[j] = A[i1];
i1 = i1 + 1;
}
}
}
CopyArray(B[], iBegin, iEnd, A[])
{
for(k = iBegin; k < iEnd; k++)
A[k] = B[k];
}
3. 实现快速排序算法
要求：实现QuickSort 算法。
输入：待排数据文件data.txt；
输出：有序数据文件resultsQS.txt（注：建议将此排好序的数据作为实验二的算法输入）；程序运行时间TimeQS。
快速排序算法（伪码）：
Procedure QuickSort(p, q)
integer p, q；global n, A(1:n)
if p< q then
j ← q+1
Partition(p, j); //用元素A(p)划分元素表A[p : j-1]；划分后，划分元素下标由参数j带出。
QuickSort (p, j-1);
QuickSort(j+1, q);
end if
end QuickSort
用元素A(m)划分元素表A[m : p-1]：
Procedure partition(m, p)
integer m, p, I; global A(m:p-1)
v=A(m); I=m;
loop
loop I=I+1 until A(I)>=v repeat
loop p=p-1 until A(p)<=v repeat
if I<p
then A(i) « A(p)
else exit
end if
repeat
A(m)=A(p); A(p)=v;
end partition
四、TimeIS、TimeQS的记录结果:
实验结果分析：
快速排序在一般情况下的时间效率明显优于合并排序；这个结果也与我们的理论分析结果一致。
五、实验心得：
本次实验我对以前的排序有了更深的了解，这次是合并排序和快速排序的比较，从效率上看快排的平均时间相对要少一些，从时间的分析，看出来的，这次实验也让自己的动手难呢过力变得更好，也对一个程序完整的流程图有一定的了解。
程序清单：
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
main( )
{
int i;
FILE *fp;//建立一个文件操作指针
fp=fopen("data.txt","w+");//以追加的方式建立或打开1.txt
srand( (unsigned)time( NULL ) );
for( i = 0; i < 2000;i++ )//产生2000个1-10000的随机数
fprintf(fp,"%d\n", rand()%10000+1);//输出到文本中
fclose(fp);
}
快速排序：
#include <stdio.h>
void quick (int *p,int left,int right);
int main(void)
{
int i;
int a[2000];//开一个足够大的数组。
int k = 0;
FILE *fp;//文件指针
fp = fopen("data.txt", "r");//以文本方式打开文件。
if(fp == NULL) //打开文件出错。
return -1;
while(fscanf(fp, "%d", &a[k]) != EOF) //读取数据到数组，直到文件结尾(返回EOF)
k++;
fclose(fp);//关闭文件
quick(a,0,1999);
for (i = 0; i <2000; i++)
{
printf("%d,",a[i]);
}
return 0;
}
void quick(int *p, int left,int right)
{
if(left < right)
{
int i,j;
int key;
key = p[left];
j = right;
i = left;
while(i < j)
{
while(i < j && p[j] >= key)
j--;
p[i] = p[j];
while(i < j && p[i] < key)
i++;
p[j] = p[i];
}
p[i] = key;
quick(p,left,i - 1);
quick(p,i + 1,right);
}
}
合并：
#include<stdio.h>
// 一个递归函数
void mergesort(int *num,int start,int end);
// 这个函数用来将两个排好序的数组进行合并
void merge(int *num,int start,int middle,int end);
int main()
{
// 测试数组
int num[10]= {12,54,23,67,86,45,97,32,14,65};
int i;
// 排序之前
printf("Before sorting:\n");
for (i=0; i<10; i++)
{
printf("%3d",num[i]);
}
printf("\n");
// 进行合并排序
mergesort(num,0,9);
printf("After sorting:\n");
// 排序之后
for (i=0; i<10; i++)
{
printf("%3d",num[i]);
}
printf("\n");
return 0;
}
//这个函数用来将问题细分
void mergesort(int *num,int start,int end)
{
int middle;
if(start<end)
{
middle=(start+end)/2;
// 归并的基本思想
// 排左边
mergesort(num,start,middle);
// 排右边
mergesort(num,middle+1,end);
// 合并
merge(num,start,middle,end);
}
}
//这个函数用于将两个已排好序的子序列合并
void merge(int *num,int start,int middle,int end)
{
int n1=middle-start+1;
int n2=end-middle;
// 动态分配内存，声明两个数组容纳左右两边的数组
int *L=new int[n1+1];
int *R=new int[n2+1];
int i,j=0,k;
//将新建的两个数组赋值
for (i=0; i<n1; i++)
{
*(L+i)=*(num+start+i);
}
// 哨兵元素
*(L+n1)=1000000;
for (i=0; i<n2; i++)
{
*(R+i)=*(num+middle+i+1);
}
*(R+n2)=1000000;
i=0;
// 进行合并
for (k=start; k<=end; k++)
{
if(L[i]<=R[j])
{
num[k]=L[i];
i++;
}
else
{
num[k]=R[j];
j++;
}
}
delete [] L;
delete [] R;
}
第二篇：算法分析与设计实验报告-合并排序、快速排序
实验报告
实验一 合并排序、快速排序
一．实验目的
（1） 学习合并排序和快速排序算法的思想，掌握原理。
（2） 运用合并排序和快速排序算法的思想进行编程实现，以加深理解。
二．实验内容
（1）输入几个整数，运用合并排序的思想进行编程实现，输出正确的排序结果。
（2）输入10个整数，运用快速排序的思想进行编程实现，输出正确的排序结果
三．实验代码
(1)合并排序源代码如下：
#include <iomanip.h>//调用setw
#include <iostream.h> //将b[0]至b[right-left+1]拷贝到a[left]至a[right]
template <class T>
void Copy(T a[],T b[],int left,int right)
{ int size=right-left+1;
for(int i=0;i<size;i++)
{
a[left++]=b[i];
}
} //合并有序数组a[left:i],a[i+1:right]到b,得到新的有序数组b
template <class T>
void Merge(T a[],T b[],int left,int i,int right)
{ int a1cout=left,//指向第一个数组开头
a1end=i,//指向第一个数组结尾
a2cout=i+1,//指向第二个数组开头
a2end=right,//指向第二个数组结尾
bcout=0;//指向b中的元素
for(int j=0;j<right-left+1;j++)//执行right-left+1次循环
{ if(a1cout>a1end)
{ b[bcout++]=a[a2cout++];
continue; } //如果第一个数组结束，拷贝第二个数组的元素到b
if(a2cout>a2end)
{
b[bcout++]=a[a1cout++];
continue; } //如果第二个数组结束，拷贝第一个数组的元素到b
if(a[a1cout]<a[a2cout])
{ b[bcout++]=a[a1cout++];
continue; } //如果两个数组都没结束，比较元素大小，把较小的放入b
else
{ b[bcout++]=a[a2cout++];
continue;} } } //对数组a[left:right]进行合并排序
template <class T>
void MergeSort(T a[],int left,int right)
{ T *b=new
int[right-left+1];
if(left<right)
{
int i=(left+right)/2;//取中点
MergeSort(a,left,i);//左半边进行合并排序
MergeSort(a,i+1,right);//右半边进行合并排序
Merge(a,b,left,i,right);//左右合并到b中
Copy(a,b,left,right);//从b拷贝回来
}
}
int main()
{ int n;
cout<<"请输入您将要排序的数目:"; cin>>n;
int *a=new int[n]; cout<<"请输入相应的数字：";
for(int i=0;i<n;i++)
{ cin>>a[i]; }
MergeSort( a, 0, n-1); cout<<"排序结果:";
for(int j=0;j<n;j++)
{ cout<<setw(5)<<a[j]; }
cout<<endl;
return 1;
}
（2）快速排序源代码如下：
#include <iostream.h>
#define MAX 10
int QuickSort(int a[],int l,int r)
{
int pivot; //枢轴
int i=l;
int j=r;
int tmp;
pivot=a[(l+r)/2];//取数组中间的数为枢轴
do {
while (a[i]<pivot) i++; //i右移
while (a[j]>pivot) j--; // j左移
if (i<=j)
{
tmp=a[i];
a[i]=a[j];
a[j]=tmp; //交换a[i]和a[j]
i++;
j--;
}
} while(i<=j);
if (l<j) QuickSort(a,l,j);
if (i<r) QuickSort(a,i,r);
return 1;
}
int main()
{
int array[MAX];
int i;
cout<<"请输入"<<MAX<<" 个整数:";
for (i=0;i<MAX;i++)
cin>>array[i];
QuickSort(array,0,MAX-1);
cout<<"快速排序后："<<endl;
for (i=0;i<MAX;i++)
cout<<array[i]<<" ";
cout<<endl;
return 0;
}
四．实验结果
五．总结与思考