(即待求解问题的描述、算法设计、算法描述、算法正确性证明、算法分析、算法实现与测试),针对快速排序算法从实践中理解分治法的思想、求解策略及步骤。实验目的理解分治法的核心思想以及分治法求解过程;从算法分析与设计的角度,对快速排序算法有更进一步的理解。环境要求 对于环境没有特别要求。对于算法实现,可以自由选择C,C++,Java,甚至于其他程序设计语言。实验步骤步骤1:理解问题,给出问题的描述。步骤2:算法设计,包括策略与数据结构的选择步骤3:描述算法。希望采用源代码以外的形式,如伪代码、流程图等;步骤4:算法的正确性证明。需要这个环节,在理解的基础上对算法的正确性给予证明;步骤5:算法复杂性分析,包括时间复杂性和空间复杂性;步骤6:算法实现与测试。附上代码或以附件的形式提交,同时贴上算法运行结果截图;步骤7:技术上、分析过程中等各种心得体会与备忘,需要言之有物。 说明:步骤1-6在“实验结果”一节中描述,步骤7在“实验总结”一节中描述。实验结果问题描述快速排序是一种划分交换排序,其基本思想是:通过一趟扫描将待排序的元素分割成独立的三个序列:第一个序列中所有元素均不大于基准元素、第二个序列是基准元素、第三个序列中所有元素均不小于基准元素。由于第二个序列已经处于正确位置,因此需要再按此方法对第一个序列和第三个序列分别进行排序,整个排序过程可以递归进行,最终可使整个序列变成有序序列。算法设计快速排序采用分治策略快速排序的基本思想是基于分治策略的,利用分治法可将快速排序的基本思想描述如下:设当前排序的序列为R【low:high】,其中low<=high,如果序列的规模足够小则直接进行排序,否则分三步处理:A分解B求解子问题C合并描述算法void QuickSort(int R[],int low,int high){ int pivotpos; //划分后的基准元素所对应的位置 if(low<high)//仅当区间长度大于1时才须排序{ pivotpos=Partition(R,low,high); QuickSort(R,low,pivotpos-1); //对左区间递归排序QuickSort(R,pivotpos+1,high); //对右区间递归排序 }} 正确
基于分治法的快速排序 来自淘豆网m.daumloan.com转载请标明出处.