文档介绍：(用分治法实现快速排序算法)实验目的通过上机实验,要求掌握分治算法的问题描述、算法设计思想、程序设计。实验原理给定任意几组数据,利用分治法的思想,将数据进行快速排序并将排好的数据进行输出。程序思想:通过一趟排序将要排序的数据分割成独立的两部分, 其中一部分的所有数据都比另外一部分的所有数据都要小, 然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。快速排序算法的性能取决于划分的对称性。通过修改函数 Partition,可以设计出采用随机选择策略的快速排序算法。实验步骤分解:以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]中任何一个元素大于等于a[q]。下标q在划分过程中确定。递归求解:通过递归调用快速排序算法分别对 a[p:q-1]和a[q+1:r]进行排序。合并:由于对a[p:q-1]和a[q+1:r]的排序是就地进行的,所以在 a[p:q-1]和a[q+1:r]都已排好的序后,不需要执行任何计算, a[p:r]就已排好序。关键代码//函数Partition 以一个确疋的基准兀素a[p]对子数组a[p:r]进行划分template<classType>intPartition(Typea[], intp,intr){inti=p,j=r+1;Typex=a[p];//将<x的元素交换到左边区域//将>乂的元素交换到右边区域while(true){while(a[++i]<x&&i<r);while(a[--j]>x);if(i>=j){break;}Swap(a[i],a[j]);}a[p]=a[j]; //将基准元素放在合适的位置a[j]=x;returnj;}//通过RandomizedPartition函数来产生随机的划分templatevclassType>intRandomizedPartition(Typea[],intp,intr){inti=Random(p,r);Swap(a[i],a[p]);returnPartition(a,p,r);}较小个数排序序列的结果:测试结果较大个数排序序列的结果:序审序灵亍熱116131882B2575?5 79566446889S8B15212683J69071844170S375C95231742469Lfi69263GG?3912S2B心419B3b6S?11lb1H2121聽2bZfeZ#姑跖31dl41134b吕盘!>& b!69盟6?7B70717374797?«38J84WE089B?1»39STheCineitB.***@20请按任意融绒■…■实验心得快速排序在之前的数据结构中也是学过的,在几大排序算法中,快速排序和归并排序尤其是重中之重,之前的快速排序都是给定确定的轴值,所以存在一些极端的情况使得时间复杂度很高,排序的效果并不是很好,现在学习的一种利用随机化的快速排序算法,通过随机的确定轴值,从而可以期望划分是较对称的,减少了出现极端情况的次数, 使得排序的效率挺高了很多,化算法想呼应,而且关键的是对于随机生成函数, 通过这