算法分析与设计实验报告合并排序、

实验报告

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

一．实验目的

（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;}/如果第一个数组结束，拷贝第二个数组的元素到bif(a2cout>a2end)

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

continue;}/如果第二个数组结束，拷贝第一个数组的元素到bif(a[a1cout]

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

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

else

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

continue;}}}/对数组a[left:right]进行合并排序template

voidMergeSort(Ta[],intleft,intright)

{Tb=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;inta=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

defineMA_10

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[MA_];

inti;

cout<<"请输入"<

cin>array[i];

QuickSort(array,0,MA_-1);cout<<"快速排序后："<

cout<

return0;

四．实验结果

五．总结与思考