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

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

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

#include<

iomanip.h>

//调用setw

iostream.h>

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

template<

classT>

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

{intsize=right-left+1;

for（inti=0;

i<

size;

i++）

{

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

}

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

i],a[i+1:

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

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

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

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

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

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

bcout=0;

//指向b中的元素

for（intj=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]进行合并排序

voidMergeSort（Ta[],intleft,intright）

{T*b=new

int[right-left+1];

if（left<

right）

{

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

请输入相应的数字：

for（inti=0;

{cin>

a[i];

}

MergeSort（a,0,n-1）;

cout<

排序结果:

for（intj=0;

j++）

{cout<

setw（5）<

a[j];

}

cout<

endl;

return1;

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

#defineMAX10

intQuickSort（inta[],intl,intr）

{

intpivot;

//枢轴

inti=l;

intj=r;

inttmp;

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

return1;

}

intmain（）

intarray[MAX];

inti;

cout<

请输入"

MAX<

个整数:

for（i=0;

MAX;

i++）

cin>

array[i];

QuickSort（array,0,MAX-1）;

cout<

快速排序后：

cout<

array[i]<

"

return0;

四．实验结果

五．总结与思考