分治法实现快速排序.doc

实验一实验名称： 利用分治法实现快速排序 实验时间: 2012年12月 成绩： 一、实验目的 分治法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同。递归地解这些子问题，然后将各个子问题的解合并得到原问题的解。 本实验的目的是利用分治策略实现快速排序算法。二、实验内容快速排序算法是基于分治策略的排序算法。其基本思想是，对于输入的子数组ap:r,按以下三个步骤进行排序。（1）分解：以ap为基准元素将ap:r划分成3段ap:q-1,aq和aq+1:r，使ap:q-1中任何一个元素小于等于aq，而aq+1:r中任何一个元素大于等于aq。下标q在划分过程中确定。（2）递归求解：通过递归调用快速排序算法分别对ap:q-1和aq+1:r进行排序。（3）合并：由于对ap:q-1和aq+1:r的排序是就地进行的，所以在ap:q-1和aq+1:r都已排好的序后，不需要执行任何计算，ap:r就已排好序。基于这个思想，可实现的快速排序算法如下：void QuickSort(int a,int p,int r) if(pr)int q=Partition(a,p,r); QuickSort(a,p,q-1);QuickSort(a,q+1,r);对含有n个元素的数组a0;n-1进行快速排序只要调用QuickSort(a,0,n-1)即可。上述算法中的函数Partition，以确定的一个基准元素ap对子数组ap:r进行划分，它是快速排序算法的关键。int Partition(int a,int p,int r) int i=p,j=r+1;int x=ap;while(true)while(a+ix&ix);if(i=j) break;Swap(ai,aj); ap=aj;aj=x;return j; Partition对ap:r进行划分时，以元素x=ap作为划分的基准，分别从左、右两端开始，扩展两个区域ap:i和aj:r,使ap:i中元素小于或等于x，而aj:r中元素大于或等于x。初始时，i=p,且j=r+1。在while循环体中，下标j逐渐减小，i逐渐增大，直到ai=x=aj。此时若i=j时结束。这时ap:r已被划分成ap:q-1,aq和aq+1:r,且满足ap:q-1中元素不大于aq+1：r中元素。在Partition结束时返回划分点q=j。三、实验过程#includeusing namespace std;inline void Swap(int &x,int &y) /交换x,yint temp=x;x=y;y=temp;int Partition(int a,int p,int r) /Partition 以确定一个基准元素aq对子数组ap:r进行划分int i=p,j=r+1;int x=ap;/将x得元素交换到右边区域while(true)while(a+ix&ix);if(i=j) break;Swap(ai,aj); /交换ai,ajap=aj;aj=x;return j; /返回划分点void QuickSort(int a,int p,int r) /利用递归进行快速排序if(pr)int q=Partition(a,p,r); /Partition返回划分点j，此处使q=jQuickSort(a,p,q-1);QuickSort(a,q+1,r);int main() int len;coutlen;int *a=new intlen; /动态生成一个长度为len的数组cout请输入一个数组: ; for(int i=0;iai;QuickSort(a,0,len-1); /对数组进行快排cout排序后的数组是:;for(int j=0;jlen;j+)coutaj ; /输出数组coutendl;delete