南昌航空大学实验报告.doc

南昌航空大学实验报告
年月口
课程名称：算法设计与分析 实验名称:快速排序
班级：11201221姓名:林平君同组人:
指导教师评定：签名：
实验目的
对快速排序进行了解
将算法用程序代码实现。
分析算法实现的效率。
实验要求
理解减治法的思想
理解快速排序的思想
算法效率分析
Log2n
源代码
如下：
public class Quicksort {
/枠第八次实验
* @ param args
*/
public static void main(String[l args) { int [”{6,2,7,3,8,9};
// int []b=new int[6]; qsort(a, 0, a」ength-1);
(M,,+nerrors?n);
)
public static void qsort(int a[] jnt left,int right) {
left=O;
right=-l;
int dp;
if(left<right) dp=partition(a, left, right); qsort(a, left, dp-1); qsort(a, dp+1, right);
}
else{
for(int i=O;i<;i++) {
(a[i]+"U);
)
public static int partition(int a[],int left,int right) {
left=O;
right= ngth-1;
int pivot=a[leftl;
while(left<right)
right-;
} if(left<right)
{
a[right++]=pivot;
}
vvhile(left<right && a[left]v二pivot)
{
left++;
} if(left<right)
{
a[left++]=pivot;
}
}
a[left]=pivot;
return left;
心得体会
通过本次实验，深一步的了解了减治法的分析过程，利用减治法 可以降低算法的运行效率，提高程序的运行速度。