基于分治法的快速排序_分治法实现快速排序

基于分治法的快速排序由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“分治法实现快速排序”。

实验2.基于分治法的快速排序算法

实验内容

本实验要求基于算法设计与分析的一般过程（即待求解问题的描述、算法设计、算法描述、算法正确性证明、算法分析、算法实现与测试），针对快速排序算法从实践中理解分治法的思想、求解策略及步骤。

实验目的 理解分治法的核心思想以及分治法求解过程；

 从算法分析与设计的角度，对快速排序算法有更进一步的理解。

环境要求

对于环境没有特别要求。对于算法实现，可以自由选择C, C++, Java，甚至于其他程序设计语言。

实验步骤

步骤1：理解问题，给出问题的描述。

步骤2：算法设计，包括策略与数据结构的选择

步骤3：描述算法。希望采用源代码以外的形式，如伪代码、流程图等； 步骤4：算法的正确性证明。需要这个环节，在理解的基础上对算法的正确性给予证明； 步骤5：算法复杂性分析，包括时间复杂性和空间复杂性；

步骤6：算法实现与测试。附上代码或以附件的形式提交，同时贴上算法运行结果截图;步骤7：技术上、分析过程中等各种心得体会与备忘，需要言之有物。

说明：步骤1-6在“实验结果”一节中描述，步骤7在“实验总结”一节中描述。

实验结果

问题描述

快速排序是一种划分交换排序，其基本思想是：通过一趟扫描将待排序的元素分割成独立的三个序列：第一个序列中所有元素均不大于基准元素、第二个序列是基准元素、第三个序列中所有元素均不小于基准元素。由于第二个序列已经处于正确位置，因此需要再按此方法对第一个序列和第三个序列分别进行排序，整个排序过程可以递归进行，最终可使整个序列变成有序序列。算法设计

快速排序采用分治策略

快速排序的基本思想是基于分治策略的，利用分治法可将快速排序的基本思想描述如下：设当前排序的序列为R【low：high】，其中low

A分解B求解子问题C合并 描述算法

void QuickSort(int R[]，int low，int high){

int pivotpos； //划分后的基准元素所对应的位置

if(low

pivotpos=Partition(R,low,high)；

QuickSort(R,low,pivotpos-1)；

//对左区间递归排序

QuickSort(R,pivotpos+1,high)；

//对右区间递归排序

} } 正确性证明

原始序列： 49 38 65 97 76 13 27 第一次扫描：

[27 38 13] 49 [76 97 65] 以27为基准元素

得到的序列: [13] 27 [38] 以76为基准元素

得到的序列：[65] 76 [97] 最终序列为：、27、38、49、65、76、97

算法复杂性分析

最坏情况O(n2)

ìO(1)n=1ïT(n)=íïîT(n-1)+O(n)n>1最好情况O(nlogn)

平均情况：O(nlogn)

1nT(n)=å(T(n-k)+T(k-1))+nnk=1 ìO(1)n=1ïT(n)=íïî2T(n/2)+O(n)n>1空间复杂性：

由于快速排序算法是递归执行，需要一个栈来存放每一层递归调用的必要信息，其最大容量应与递归调用的深度一致。最好情况下，若每次划分较为均匀，则递归树的高度为O（logn），故递归所需栈空间为O（logn）。最坏情况下，递归树的高度为O（n）,所需的栈空间同为O（n）.平均情况下，所需栈空间为O（logn）。

算法实现与测试

实验总结

在学数据结构这门课时，我们就学过多种排序，像冒泡排序，递归排序，堆栈排序，归并排序，快速排序等。这次的基于分治法的快速排序相对能熟悉一些，关键是依据所选的基准元素对序列进行划分即可。