实验报告-归并快速排序

《算法设计与分析》实验报告一学号：1004091130姓名：金玉琦日期：2011-10-13得分：一、实验内容：归并排序与快速排序。二、所用算法的根本思想及复杂度分析：1.分治法分治法的设计思想是将一个难以直接解决的大问题，划分成一些规模较小的问题，以便各个击破，分而治之。2.归并排序1〕根本思想归并排序其分治策略如下：划分：将待排序的序列从n/2处划分为两个长度相等的序列。求解子问题：分别对这两个子序列进行归并排序，得到两个有序子序列。合并：将这两个有序子序列合并成一个有序序列。2〕复杂度分析二路归并排序的合并步的时间复杂度为O(n)，所以，二路归并排序算法存在如下递推式： 1 n=2T(n)= 2T(n/2)+n n>2将上式进行迭代运算，计算的二路归并排序的时间代价是O(nlogn)。二路归并排序归并过程中需要与原始记录序列同样数量的存储空间，因此其空间复杂度为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)+nlogn=O(nlogn)因此时间复杂度是O(nlogn)。在最坏的情况下，待排序的记录为正序或逆序时，时间复杂度为O(n)。由于快速排序是递归执行，需要一个栈存放每一层递归调用的必要信息，其最大的容量应该与递归调用的深度一致。最好情况因为要进行logn次递归调用，栈的深度是O(logn)；最坏的情况下，进行n-1次调用，所以栈的深度为O(n)。三、源程序及注释：1、归并排序voidMergeSort(intr[],intrl[],ints,intt){ intm; 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、合并有序子序列voidMerge(intr[],intrl[],ints,intm,intt){ inti=s; intj=m+1; intk=s; while(i<=m&&j<=t) { if(r[i]<=r[j]) rl[k++]=r[i++]; //取r[i]和r[j]中较小的放入rl[k]中 else rl[k++]=r[j++]; } if(i<=m) { while(i<=m) rl[k++]=r[i++];//假设第一个子序列没有处理完，进行收尾处理 } else { while(j<=t) rl[k++]=r[j++];//假设第二个子序列没有处理完，进行收尾处理 } for(intn=s;n<=t;n++) { r[n]=rl[n]; //将合并完成后的rl[]序列送回r[]序列中 }}3、快速排序voidQuickSort(intr[],intfirst,intend){ intpivot; if(first<end) { pivot=Partition(r,first,end); //pivot是轴值在序列中位置 QuickSort(r,first,pivot-1); //递归左侧序列进行快排 QuickSort(r,pivot+1,end); //递归右侧序列进行快排 }}快速排序的一次划分intPartition(intr[],intfirst,intend){ inti=first; intj=end; //初始化 inttemp=0; while(i<j) { while(i<j&&r[i]<=r[j])j--; //从右侧扫描 if(i<j) { temp=r[i]; r[i]=r[j]; r[j]=temp; //将较小的记录交换到前面 i++; } while(i<j&&r[i]<=r[j])i++; //从左侧扫描 if(i<j) { temp=r[i]; r[i]=r[j]; r[j]=temp; //将较小的记录交换到后面 j--; } } returni; //返回轴值的最终位置}四、运行输出结果：五、调试和运行程序过程中产生的问题、采取的措施及获得的相关经验教训：调试过程中