算法分析與設(shè)計 實驗二

洛陽理工學(xué)院驗報告系部

計算機(jī)系

班級

學(xué)號

姓名課程名稱實驗名稱

算法分析與設(shè)計分治法（一）

實驗日期成績實驗?zāi)康模?.掌握分治算法的原理。2.能用程序設(shè)計語言實現(xiàn)快速排序的算法。實驗條件：電腦一臺，實驗內(nèi)容與步驟：內(nèi)容：1．速排序。快速排序是C.R.A.Hoare于1962年出的一種劃分交換排序采了一種分治的策略常稱其為分治法(Divide-and-ConquerMethod)。該方法的基本思想是：．先從數(shù)列中取出一個數(shù)作為基準(zhǔn)數(shù)。．分區(qū)過程，將比這個數(shù)大的數(shù)全放到它的右邊，小于或等于它的數(shù)全放到它的左。．再對左右區(qū)間重復(fù)第二步，直到各區(qū)間只有一個數(shù)。1.voidints[],intintr)2.{3.if(l<4.{5.6.

inti=partition(s,l,劃分函數(shù)quick_sort1(s,l,i-//遞歸調(diào)用7.quick_sort1(s,ir);8.}9.}步驟：1.主數(shù)。2.(1)劃函數(shù)Partition();選第一個數(shù)為基準(zhǔn)。(2)intRandomizedPartition(Typep,intr)

編寫隨機(jī)劃分函數(shù)TypeRandomizedSelect(Typep,intr,intk);

隨機(jī)選擇函數(shù)intRandom(intx,inty)

產(chǎn)生x,y之的隨機(jī)數(shù)

voidSwap(Type&y)

交換x,y的main():inta[N],隨機(jī)生成一數(shù)，調(diào)用快速排序進(jìn)行排序。3.單步調(diào)試，觀察程序的執(zhí)行過程。運(yùn)行結(jié)果：實驗總結(jié)：

附：源程序：#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

繼續(xù)右移\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);

繼續(xù)左移\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);//快速排序調(diào)用//輸出排序后的結(jié)果printf("*************