实验报告归并快速排序

《算法设计与分析》实验报告⼀学号： 1004091130 姓名：⾦⽟琦⽇期：2011-10-13得分：⼀、实验内容：归并排序与快速排序。

⼆、所⽤算法的基本思想及复杂度分析：1.分治法

分治法的设计思想是将⼀个难以直接解决的⼤问题，划分成⼀些规模较⼩的问题，以便各个击破，分⽽治之。2.归并排序1）基本思想

归并排序其分治策略如下：

划分：将待排序的序列从n/2处划分为两个长度相等的序列。

求解⼦问题：分别对这两个⼦序列进⾏归并排序，得到两个有序⼦序列。合并：将这两个有序⼦序列合并成⼀个有序序列。2）复杂度分析

⼆路归并排序的合并步的时间复杂度为O(n)，所以，⼆路归并排序算法存在如下递推式：1 n=2T(n)=2T(n/2)+n n>2

n)。⼆路归并排序归将上式进⾏迭代运算，计算的⼆路归并排序的时间代价是O(nlog2

并过程中需要与原始记录序列同样数量的存储空间，因此其空间复杂度为O(n)。3.快速排序1）基本思想

快速排序的分治思想如下：

划分：选定⼀个记录作为轴值，以轴值为基准将整个序列划分成两个⼦序列，轴值的位置i在划分过程中确定，并且前⼀个⼦序列中的记录的值均⼩于或等于轴值，后⼀个⼦序列的记录的值均⼤于或等于轴值。求解⼦问题：分别对划分后的每⼀个⼦序列递归处理。

合并：将轴值前后的⼦序列的排序是就地进⾏的，所以合并不需要执⾏任何操作。2）复杂度分析

在最好的情况下每次划分对⼀个记录定位后，该记录的左右两侧⼦序列的长度相同。在具有n个记录的序列中，⼀次划分需要对整个带排序的序列扫描⼀遍，所需时间为O(n)。设T(n)是对n个记录的序列进⾏排序的时间，每次划分后，正好把带划分的区间划分为长度相同的两个⼦序列，则有：T(n)≤2T(n/2)+n

≤2(2T(n/4)+n/2)+n=4T(n/4)+2n

≤4(2T(n/8)+n/4)+2n=8T(n/8)+3n……≤nT(1)+ nlog2n=O(nlog2n)

因此时间复杂度是O(nlog2n)。

在最坏的情况下，待排序的记录为正序或逆序时，时间复杂度为O(n2)。

由于快速排序是递归执⾏，需要⼀个栈存放每⼀层递归调⽤的必要信息，其最⼤的容量应该与递归调⽤的深度⼀致。最好情况因为要进⾏log2

n次递归调⽤，栈的深度是O(log2

n)；最坏的情况下，进⾏n-1次调⽤，所以栈的深度为O(n)。三、源程序及注释：1、归并排序

void MergeSort(int r[],int rl[],int s,int t){int m;if(s==t)rl[s]=r[s];else{

m=(s+t)/2;

MergeSort(r,rl,s,m); //归并排序前半个⼦序列MergeSort(r,rl,m+1,t); //归并排序后半个⼦序列Merge(rl,r,s,m,t); //合并两个已排序的⼦序列}}

2、合并有序⼦序列

void Merge(int r[],int rl[],int s,int m,int t){

int i=s;int j=m+1;int k=s;

while (i<=m&&j<=t){

if(r[i]<=r[j])

rl[k++]=r[i++]; //取r[i]和r[j]中较⼩的放⼊rl[k]中elserl[k++]=r[j++];}if(i<=m){

while(i<=m)

rl[k++]=r[i++];//若第⼀个⼦序列没有处理完，进⾏收尾处理}else{

while(j<=t)

rl[k++]=r[j++];//若第⼆个⼦序列没有处理完，进⾏收尾处理}for (int n=s;n<=t;n++){

r[n]=rl[n]; //将合并完成后的rl[]序列送回r[]序列中}}

3、快速排序

void QuickSort(int r[],int first,int end){int pivot;if (first{

pivot=Partition(r,first,end); //pivot是轴值在序列中位置QuickSort(r,first,pivot-1); //递归左侧序列进⾏快排QuickSort(r,pivot+1,end); //递归右侧序列进⾏快排}}

1、快速排序的⼀次划分int Partition(int r[],int first,int end){int i=first;

int j=end; //初始化int temp=0;while (i{while(iif (i{temp=r[i];r[i]=r[j];

r[j]=temp; //将较⼩的记录交换到前⾯i++;}while(iif (i{temp=r[i];r[i]=r[j];

r[j]=temp; //将较⼩的记录交换到后⾯j--;}}

return i; //返回轴值的最终位置}四、运⾏输出结果：

五、调试和运⾏程序过程中产⽣的问题、采取的措施及获得的相关经验教训：

调试过程中，给出随机排列的序列时，归并排序与快速排序的排序时间相差较少。但在给出的逆序序列排序时，快速排序所⽤时间明显⽐归并排序所⽤时间少。造成这种情况的原因是快速排序的轴值位置并不是将序列分成长度相等的两个部分，归并排序并

不受序列顺序或逆序的影响。