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

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=\

static String path1=\归并排序.txt\ static String path2=\快速排序.txt\ static String path3=\插入排序.txt\ static String path4=\归并排序1.txt\ static int Ar[]=new int[30005]; static int A []=new int[30005]; static int B []=new int[30005]; static int C []=new int[30005];

public static void qkWenben (String m)throws Exception { FileOutputStream testfile=new FileOutputStream(m); testfile.write(new String(\ } /* * 清空static数组 * */

public int[] qingkong(int q[]) { int b[]=new int[q.length]; for(int i=0;i

* 将排好序的数组写入文本 * */

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(a[i]));//写入文件是以字符串的形式输入的； bw.newLine(); bw.close(); fw.close(); }

catch(IOException e) { e.printStackTrace(); } }

} /*

*RandomFuction函数

*实现随机产生任意num个1~m范围的数字， *并以String的格式存入文件当中 */

public static void RandomFuction(int m,int num) { int number; Random random=new Random(); for(int i=0;i

* 将随机数从文件中读出来并存入数组当中；

* */

public int[] Reader() { int count=1; File a=new File(path); try { BufferedReader br=new BufferedReader(new FileReader(a)); while(br.ready()) { String line=br.readLine(); int num1=Integer.parseInt(line); Ar[count]=num1; count++; } } catch(IOException e) { e.printStackTrace(); } return Ar; } /* *

* 插入排序算法 * * */

public void InsertSort(int Ar1[],int n) {

int key; int i,j;

for(j=2;j<=n;j++) { i=j-1; key=Ar1[j]; while(i>0&&Ar1[i]>key) { Ar1[i+1]=Ar1[i]; i=i-1; } Ar1[i+1]=key;

} } /*

* 快速排序 * * */

public int partition(int Ar[],int p,int r) { int key; int x=Ar[r],j; int i=p-1; for(j=p;j<=r-1;j++) { if(Ar[j]<=x) { i=i+1; key=Ar[i]; Ar[i]=Ar[j]; Ar[j]=key; } } key=Ar[i+1]; Ar[i+1]=Ar[r]; Ar[r]=key; return i+1; }

public void quicksort(int Ar[],int p,int r) { int q; if(p

* 归并排序 * */

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 int[n1+2]; R1=new int[n2+2]; for(i=1;i<=n1;i++) { L1[i]=Ar[p+i-1]; }

for(j=1;j<=n2;j++) { R1[j]=Ar[q+j]; }

L1[n1+1]=100000;//因为生成的随即数是0-30000范围内的数据 R1[n2+1]=100000; i=1; j=1; for(k=p;k<=r;k++) { if(L1[i]<= R1[j]) { Ar[k]=L1[i]; i=i+1; } else { Ar[k]=R1[j]; j=j+1; } } } public void MergeSort(int Ar[],int p,int r) { int q; if(p

{ /* }

/*

* 把data[i..m]和data[m+1..j]归并

* 放到temp1[0..m-i]和temp2[0..j-m-1]中 * 归并到temp[0..j-i]中 * 然后复制到data[i..j]中 * * */

int[] temp1,temp2,temp; temp1=new int[m-i+1+1]; temp2=new int[j-m-1+1+1]; temp=new int[j-i+1];

for(int count=0;count

temp1[count]=data[count+i]; }

temp1[m-i+1]=100000;

for(int count=0;count

temp2[count]=data[count+m+1]; }

temp2[j-m]=100000;

int index1=0,index2=0;

for(int count=0;count

for(int count=0;count

data[i+count]=temp[count]; }

public static void mergeSort(int[] data, int i, int j) { if(i

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(\输入要产生的随机数的范围（0~m）上限m\ m=sac.nextInt();

RandomFuction(m,num); Ar=br.qingkong(Ar); Ar=br.Reader();

t2=System.currentTimeMillis();

System.out.println(\运行此程序所用的时间是\。\计算程序所用 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++) { A[e]=Ar[e]; } 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(\运行此程序所用的时间是\。\计算程序 WriterFuction(path1,num,A); /* for(int i=1;i<=num;i++) { System.out.println(A[i]); } */ break; case 2: B=br.qingkong(B); System.out.println(\【2】快速排序\ for(int e=1;e<=num;e++) { B[e]=Ar[e] ; } // 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(B[i]); }

}

}

*/

System.out.println(\运行此程序所用的时间是\。\ break; case 3: C=br.qingkong(C); System.out.println(\【3】插入排序\ for(int e=1;e<=num;e++) { C[e]=Ar[e] ; } //C=br.Reader(); t1=System.currentTimeMillis(); br.InsertSort(C,num); t2=System.currentTimeMillis(); WriterFuction(path3,num,C); /* for(int i=1;i<=num;i++) { System.out.println(C[i]); } */ System.out.println(\运行此程序所用的时间是\。\ break;

default :

System.out.println(\输入的数据应在1~3之间！\ break; }

System.out.println(\继续请输入0，否则输入其他字符结束！（1~3除外）\ zero=sac.nextInt(); }while(zero==0);

本文来源：https://www.bwwdw.com/article/y7ow.html