java实现算法导论书中的快速排序归并排序插入排序.doc

package algorithm.echo;import java.io.FileReader;import java.io.*;import java.util.Random;import java.util.Scanner;public class FirstTest /static int num;static String path=F:/b.txt;static String path1=F:/归并排序.txt;static String path2=F:/快速排序.txt;static String path3=F:/插入排序.txt;static String path4=F:/归并排序1.txt; static int Ar=new int30005; static int A =new int30005; static int B =new int30005; static int C =new int30005; public static void qkWenben (String m)throws Exception FileOutputStream testfile=new FileOutputStream(m);testfile.write(new String().getBytes(); /* * 清空static数组 * */ public int qingkong(int q) int b=new intq.length; for(int i=0;iq.length;i+) qi=bi; return q; /* * 将排好序的数组写入文本 * */ public static void WriterFuction(String m,int m1,int a) for(int i=1;i=m1;i+) try FileWriter fw=new FileWriter(m,true); BufferedWriter bw=new BufferedWriter(fw); bw.write(String.valueOf(ai);/写入文件是以字符串的形式输入的； bw.newLine(); bw.close(); fw.close(); catch(IOException e) e.printStackTrace(); /* *RandomFuction函数 *实现随机产生任意num个1m范围的数字， *并以String的格式存入文件当中 */public static void RandomFuction(int m,int num)int number;Random random=new Random();for(int i=0;inum;i+) number=random.nextInt(m); try FileWriter fw=new FileWriter(path,true); BufferedWriter bw=new BufferedWriter(fw); bw.write(String.valueOf(number);/写入文件是以字符串的形式输入的； bw.newLine(); bw.close(); fw.close(); catch(IOException e) e.printStackTrace(); /* * 将随机数从文件中读出来并存入数组当中； * */public int Reader()int count=1;File a=new File(path);tryBufferedReader br=new BufferedReader(new FileReader(a);while(br.ready()String line=br.readLine();int num1=Integer.parseInt(line);Arcount=num1;count+; catch(IOException e) e.printStackTrace(); return Ar;/* * * 插入排序算法 * * */public void InsertSort(int Ar1,int n) int key; int i,j; for(j=2;j0&Ar1ikey)Ar1i+1=Ar1i;i=i-1; Ar1i+1=key; /* * 快速排序 * * */public int partition(int Ar,int p,int r)int key;int x=Arr,j;int i=p-1;for(j=p;j=r-1;j+)if(Arj=x)i=i+1;key=Ari;Ari=Arj;Arj=key;key=Ari+1;Ari+1=Arr;Arr=key;return i+1;public void quicksort(int Ar,int p,int r)int q;if(pr)q=partition(Ar,p,r);quicksort(Ar,p,q-1);quicksort(Ar,q+1,r); /* * 归并排序 * */public void merge(int Ar,int p,int q,int r)int i,j,k,n1=q-p+1,n2=r-q;int L1,R1; L1=new intn1+2; R1=new intn2+2; for(i=1;i=n1;i+) L1i=Arp+i-1; for(j=1;j=n2;j+) R1j=Arq+j; L1n1+1=100000;/因为生成的随即数是0-30000范围内的数据 R1n2+1=100000; i=1; j=1; for(k=p;k=r;k+) if(L1i= R1j) Ark=L1i; i=i+1; else Ark=R1j; j=j+1; public void MergeSort(int Ar,int p,int r)int q;if(pr)q=(p+r)/2;MergeSort(Ar,p,q);MergeSort(Ar,q+1,r);merge(Ar,p,q,r); /*public static void merge(int data,int i,int m,int j)/* 把datai.m和datam+1.j归并* 放到temp10.m-i和temp20.j-m-1中* 归并到temp0.j-i中* 然后复制到datai.j中* * */*int temp1,temp2,temp;temp1=new intm-i+1+1;temp2=new intj-m-1+1+1;temp=new intj-i+1;for(int count=0;countm-i+1;count+) temp1count=datacount+i;temp1m-i+1=100000;for(int count=0;countj-m-1+1;count+) temp2count=datacount+m+1;temp2j-m=100000;int index1=0,index2=0;for(int count=0;countj-i+1;count+)if(temp1index1temp2index2) tempcount=temp1index1; index1+;elsetempcount=temp2index2;index2+;for(int count=0;counttemp.length;count+)datai+count=tempcount;public static void mergeSort(int data, int i, int j)if(ij)mergeSort(data,i,(i+j)/2);mergeSort(data,(i+j)/2+1,j);merge(data,i,(i+j)/2,j);*/public static void main(String args) throws Exception qkWenben(path); qkWenben(path1); qkWenben(path2); qkWenben(path3); long t1,t2; t1=System.currentTimeMillis(); int m,num,Sel;int p=1;int r,zero;FirstTest br=new FirstTest ();Scanner sac=new Scanner(System.in);System.out.println(请输入要产生的随机数的个数(num)：);num=sac.nextInt();System.out.println(输入要产生的随机数的范围（0m）上限m); m=sac.nextInt(); RandomFuction(m,num); Ar=br.qingkong(Ar); Ar=br.Reader(); t2=System.currentTimeMillis(); System.out.println(运行此程序所用的时间是+(t2-t1)+ms。);/计算程序所用的时间 r=num; do System.out.println(请选择要进行的排序：); System.out.println(【1】归并排序); System.out.println(【2】快速排序); System.out.println(【3】插入排序); Sel=sac.nextInt(); switch(Sel) case 1: A=br.qingkong(A); System.out.println(【1】归并排序); for(int e=1;e=num;e+) Ae=Are; t1=System.currentTimeMillis(); / A=br.Reader(); /* mergeSort(A,1,r/2); mergeSort(A,r/2+1,r); merge(A,1,r/2,r); */ br.MergeSort(A, 1, r); t2=System.currentTimeMillis(); System.out.println(运行此程序所用的时间是+(t2-t1)+ms。);/计算程序所用的时间WriterFuction(path1,num,A); /* for(int i=1;i=num;i+) System.out.println(Ai); */ break; case 2: B=br.qingkong(B); System.out.println(【2】快速排序); for(int e=1;e=num;e+) Be=Are ; / B=br.Reader(); t1=System.currentTimeMillis(); br.quicksort(B, p, r); t2=System.currentTimeMillis(); WriterFuction(path2,num,B); /* for(int i=1;i=num;i+) System.out.println(Bi); */ System.out.println(运行此程序所用的时间是+(t2-t1)+ms。); break; case 3: C=br.qingkong(C); System.out.println(【3】插入排序); for(int e=1;e=num;e+) Ce=Are ; /C=br.Reader(); t1=System.currentTimeMillis(); br.InsertSort(C,num); t2=System.currentTimeMillis(); WriterFuc