分治算法实验(用分治法实现快速排序算法)(共6页).doc

精选优质文档-倾情为你奉上算法分析与设计实验报告第 四 次附加实验姓名学号班级时间12.26上午地点工训楼309 实验名称分治算法实验(用分治法实现快速排序算法)实验目的通过上机实验，要求掌握分治算法的问题描述、算法设计思想、程序设计。实验原理给定任意几组数据，利用分治法的思想，将数据进行快速排序并将排好的数据进行输出。程序思想：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。快速排序算法的性能取决于划分的对称性。通过修改函数Partition，可以设计出采用随机选择策略的快速排序算法。实验步骤 分解：以ap为基准元素将ap:r划分成3段ap:q-1，aq和aq+1:r，使ap:q-1中任何一个元素小于等于aq，而aq+1:r中任何一个元素大于等于aq。下标q在划分过程中确定。