各种排序算法(插入,冒泡,合并,希尔,快速排序).doc

import java.lang.Math;public class Sort private double sortArray;public double getSortArray() return sortArray;public void setSortArray(double sortArray) this.sortArray = sortArray;/* * 输出排序样本数组 */public void PrintSortArray(double sortArray) for(int i=0; isortArray.length; i+) System.out.print(sortArrayi + );System.out.println();/* * 产生随机样本 */public double generateRandomSample(int n) sortArray = new doublen;for(int i=0; in; i+) sortArrayi = Math.random();return sortArray;/* * 插入排序 */public void insertSort(double sortArray) double key;int j; for(int i=1; i= 0)&(sortArrayj key) sortArrayj+1 = sortArrayj; j = j-1; sortArrayj+1 = key; /* * 冒泡排序 */public void bubbleSort(double sortArray) for(int i=0; isortArray.length; i+) for(int j=0; j sortArrayj+1) double temp = sortArrayj;sortArrayj = sortArrayj+1;sortArrayj+1 = temp;/* *快速排序 */public void quickSort(double sortArray, int left, int right) if(leftright)int p = partion(sortArray, left, right);quickSort(sortArray, left, p-1);quickSort(sortArray, p+1, right);public int partion(double sortArray, int left, int right) double x = sortArrayright;int i = left-1;for(int j=left; jright; j+) if(sortArrayj=x)i = i+1;double temp = sortArrayi;sortArrayi = sortArrayj;sortArrayj = temp;double temp = sortArrayi+1;sortArrayi+1 = sortArrayright;sortArrayright = temp;return i+1;/* * 合并排序 */public void mergeSort(double sortArray, int p, int r) if(pr) int q = (p+r)/2;mergeSort(sortArray, p, q);mergeSort(sortArray, q+1, r);merge(sortArray, p, q, r);public void merge (double sortArray, int p, int q, int r) int n1 = q-p+1;int n2 = r-q;double left = new doublen1+1;double right = new doublen2+1;for(int i = 0; i n1; i +)lefti = sortArrayp+i; for(int i = 0; i n2; i +)righti = sortArrayq+i+1;leftn1=Double.MAX_VALUE;rightn2=Double.MAX_VALUE;int pl = 0;int pr = 0;for(int i=p; i=r; i+) if(leftpl=rightpr)sortArrayi = leftpl;pl+;elsesortArrayi = rightpr;pr+;/* * 希尔排序 */ public void ShellSort(double a) int inc=a.length; do inc=inc/3+1; for(int start=0;start1); public void InsertSort(double a,int start,int inc) double current; int place=0; for(int i=start+inc;ia.length;i=i+inc) if(ai=start;fu=fu-inc) afu+inc=afu; if(fu=start|(afu-inccurrent) place=fu; break; aplace=current; public static void main(String args) int n = 100;double time = 0;double t1 = 0;double t2 = 0;double t3 = 0;double t4= 0;double t5 = 0;double insertArr ;double bubbleArr ;double quickArr ;double mergeArr ;double shellArr ;Sort s = new Sort();double sample = s.generateRandomSample(10);insertArr = sample;bubbleArr = sample;quickArr = sample;mergeArr = sample;shellArr = sample;System.out.println(N=10时的排序结果);System.out.println(未排序前数据为);s.PrintSortArray(sample);/排序s.insertSort(insertArr);s.bubbleSort(bubbleArr);s.quickSort(quickArr, 0, quickArr.length-1);s.ShellSort(shellArr);s.mergeSort(mergeArr, 0, mergeArr.length-1);System.out.println(插入排序结果为);s.PrintSortArray(insertArr);System.out.println(冒泡排序结果为);s.PrintSortArray(bubbleArr);System.out.println(快速排序结果为);s.PrintSortArray(quickArr);System.out.println(希尔排序结果为);s.PrintSortArray(shellArr);System.out.println(归并排序结果为);s.PrintSortArray(mergeArr);for(int j=0; j3; j+)n = n*10;for(int i=0; i5 ;i+)sample = s.generateRandomSample(n);insertArr = sample;bubbleArr = sample;quickArr = sample;mergeArr = sample;shellArr = sample;/排序,计时time = System.nanoTime();s.insertSort(insertArr);t1 += System.nanoTime() - time;time = System.nanoTime();s.bubbleSort(bubbleArr);t2 += System.nanoTime() - time;time = System.nanoTime();s.quickSort(quickArr, 0, quickArr.length-1);t3 += System.nanoTime() - time;time = System.nanoTime();s.ShellSort(shellArr);t4 += System.nanoTime() - time;time = System.nanoTime();s.mergeSort(mergeArr, 0, mergeArr.length-1);t5 += System.nanoTime() - time;t1 = t1/5;t2 = t2/5;t3 = t3/5;t4 = t4/5;t5 = t5/5;System.out.println(N= + n + 时个排序