实验报告

实验一 合并排序、快速排序

一．实验目的

（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;

}

四．实验结果

五．总结与思考