算法分析与设计实验报告-合并排序、快速排序.doc

算法分析与设计实验报告-合并排序、快速排序.doc

《算法分析与设计实验报告-合并排序、快速排序.doc》由会员分享，可在线阅读，更多相关《算法分析与设计实验报告-合并排序、快速排序.doc（3页珍藏版）》请在冰点文库上搜索。

实验报告

课程

计算机算法设计与分析

实验名称

合并排序、快速排序

学号

姓名

实验日期：

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

一．实验目的

（1）学习合并排序和快速排序算法的思想，掌握原理。

（2）运用合并排序和快速排序算法的思想进行编程实现，以加深理解。

二．实验内容

（1）输入几个整数，运用合并排序的思想进行编程实现，输出正确的排序结果。

（2）输入10个整数，运用快速排序的思想进行编程实现，输出正确的排序结果

三．实验代码

（1）合并排序源代码如下：

#include//调用setw

#include//将b[0]至b[right-left+1]拷贝到a[left]至a[right]

template

voidCopy（Ta[],Tb[],intleft,intright）

{intsize=right-left+1;

for（inti=0;i

{

a[left++]=b[i];

}

}//合并有序数组a[left:

i],a[i+1:

right]到b,得到新的有序数组b

template

voidMerge（Ta[],Tb[],intleft,inti,intright）

{inta1cout=left,//指向第一个数组开头

a1end=i,//指向第一个数组结尾

a2cout=i+1,//指向第二个数组开头

a2end=right,//指向第二个数组结尾

bcout=0;//指向b中的元素

for（intj=0;j

{if（a1cout>a1end）

{b[bcout++]=a[a2cout++];

continue;}//如果第一个数组结束，拷贝第二个数组的元素到b

if（a2cout>a2end）

{

b[bcout++]=a[a1cout++];

continue;}//如果第二个数组结束，拷贝第一个数组的元素到b

if（a[a1cout]

{b[bcout++]=a[a1cout++];

continue;}//如果两个数组都没结束，比较元素大小，把较小的放入b

else

{b[bcout++]=a[a2cout++];

continue;}}}//对数组a[left:

right]进行合并排序

template

voidMergeSort（Ta[],intleft,intright）

{T*b=new

int[right-left+1];

if（left

{

inti=（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拷贝回来

}

}

intmain（）

{intn;

cout<<"请输入您将要排序的数目:

";cin>>n;

int*a=newint[n];cout<<"请输入相应的数字：

";

for（inti=0;i

{cin>>a[i];}

MergeSort（a,0,n-1）;cout<<"排序结果:

";

for（intj=0;j

{cout<

cout<

return1;

}

（2）快速排序源代码如下：

#include

#defineMAX10

intQuickSort（inta[],intl,intr）

{

intpivot; //枢轴

inti=l;

intj=r;

inttmp;

pivot=a[（l+r）/2];//取数组中间的数为枢轴

do{

while（a[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

if（i

return1;

}

intmain（）

{

intarray[MAX];

inti;

cout<<"请输入"<

";

for（i=0;i

cin>>array[i];

QuickSort（array,0,MAX-1）;

cout<<"快速排序后：

"<

for（i=0;i

cout<

cout<

return0;

}

四．实验结果

五．总结与思考