算法分析与设计 实验二

洛阳理工学院验报告系部

计算机系

班级

学号

姓名课程名称实验名称

算法分析与设计分治法（一）

实验日期成绩实验目的：1.掌握分治算法的原理。2.能用程序设计语言实现快速排序的算法。实验条件：电脑一台，实验内容与步骤：内容：1．速排序。快速排序是C.R.A.Hoare于1962年出的一种划分交换排序采了一种分治的策略常称其为分治法(Divide-and-ConquerMethod)。该方法的基本思想是：．先从数列中取出一个数作为基准数。．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左。．再对左右区间重复第二步，直到各区间只有一个数。1.voidints[],intintr)2.{3.if(l<4.{5.6.

inti=partition(s,l,划分函数quick_sort1(s,l,i-//递归调用7.quick_sort1(s,ir);8.}9.}步骤：1.主数。2.(1)划函数Partition();选第一个数为基准。(2)intRandomizedPartition(Typep,intr)

编写随机划分函数TypeRandomizedSelect(Typep,intr,intk);

随机选择函数intRandom(intx,inty)

产生x,y之的随机数

voidSwap(Type&y)

交换x,y的main():inta[N],随机生成一数，调用快速排序进行排序。3.单步调试，观察程序的执行过程。运行结果：实验总结：

附：源程序：#include<stdio.h>intn=7;intPartition(inta[],intp,intr){inttemp,i=p,j=r+1;intx=a[p];//x=a[0];while(true){while(a[++i]<x&&i<r)printf("i=%d,j=%d--->i

继续右移\n",i,j);;while(a[--j]>x)printf("i=%d,j=%d--->jprintf("i=%d,j=%d--->",i,j);if(i>=j)break;temp=a[i];a[i]=a[j];a[j]=temp;printf("%d%d交换：",a[i],a[j]);for(inti=0;i<n;i++)printf("%d",a[i]);printf("\n");}a[p]=a[j];a[j]=x;printf("%d%d交换：",a[p],a[j]);for(i=0;i<n;i++)printf("%d",a[i]);printf("\n");returnj;}voidQuickSort(inta[],intp,intr){if(p<r){intq=Partition(a,p,r);

继续左移\n",i,j);;

printf("左子树排序\n");QuickSort(a,p,q-1);printf("右子树排序\n");QuickSort(a,q+1,r);}}voidmain(){inti;inta[]={38,32,47,31,56,78,25};printf("快速排序前：for(i=0;i<n;i++)printf("%d",a[i]);printf("\n*********************************\n");QuickSort(a,0,n-1);//快速排序调用//输出排序后的结果printf("*************