分治法实现快速排序.doc

《分治法实现快速排序.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、实验一实验名称：利用分治法实现快速排序实验时间:2012年12月成绩：一、实验目的分治法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同。递归地解这些子问题，然后将各个子问题的解合并得到原问题的解。本实验的目的是利用分治策略实现快速排序算法。二、实验内容快速排序算法是基于分治策略的排序算法。其基本思想是，对于输入的子数组a[p:r],按以下三个步骤进行排序。（1）分解：以a[p]为基准元素将a[p:r]划分成3段a[p:q-1],a[q]和a[q+1:r]，使a[p:q-1]中任何一个元素小于等于a[q]，而a[q+1:r]中任何一个

2、元素大于等于a[q]。下标q在划分过程中确定。（2）递归求解：通过递归调用快速排序算法分别对a[p:q-1]和a[q+1:r]进行排序。（3）合并：由于对a[p:q-1]和a[q+1:r]的排序是就地进行的，所以在a[p:q-1]和a[q+1:r]都已排好的序后，不需要执行任何计算，a[p:r]就已排好序。基于这个思想，可实现的快速排序算法如下：voidQuickSort(inta[],intp,intr){if(p

3、1]进行快速排序只要调用QuickSort(a,0,n-1)即可。上述算法中的函数Partition，以确定的一个基准元素a[p]对子数组a[p:r]进行划分，它是快速排序算法的关键。intPartition(inta[],intp,intr){inti=p,j=r+1;intx=a[p];while(true){while(a[++i]x);if(i>=j)break;Swap(a[i],a[j]);}a[p]=a[j];a[j]=x;returnj;}Partition对a[p:r]进行划分时，以元素x=a[p]作为划分的基准，分

4、别从左、右两端开始，扩展两个区域a[p:i]和a[j:r],使a[p:i]中元素小于或等于x，而a[j:r]中元素大于或等于x。初始时，i=p,且j=r+1。在while循环体中，下标j逐渐减小，i逐渐增大，，直到a[i]>=x>=a[j]。此时若i=j时结束。这时a[p:r]已被划分成a[p:q-1],a[q]和a[q+1:r],且满足a[p:q-1]中元素不大于a[q+1：r]中元素。在Partition结束时返回划分点q=j。三、实验过程#includeusingnam

5、espacestd;inlinevoidSwap(int&x,int&y)//交换x,y{inttemp=x;x=y;y=temp;}intPartition(inta[],intp,intr)//Partition以确定一个基准元素a[q]对子数组a[p:r]进行划分{inti=p,j=r+1;intx=a[p];//将x得元素交换到右边区域while(true){while(a[++i]x);if(i>=j)break;Swap(a[i],a[j]);//交换a[i],a[j]}a[p]=a[j];

6、a[j]=x;returnj;//返回划分点}voidQuickSort(inta[],intp,intr)//利用递归进行快速排序{if(p>len;int*a=newint[len];//动态生成一个长度为len的数组cout<<"请输入一个数组:";for(inti=0;i>a[i]

7、;QuickSort(a,0,len-1);//对数组进行快排cout<<"排序后的数组是:";for(intj=0;j