2.1.27希尔排序的用时是次平方级的。在你的计算机上用SortCompare比较希尔排序和插入排序以及选择排序。测试数组的大小按照2的幂次递增，从128开始。
shell排序的倍率是2.5，选择和插入都是在4.
public class SortCompare { ??? public static double time (String alg,Double[] a) ??? { ??????? Stopwatch timer =new Stopwatch(); ??????? if(alg.equals("Insertion")) Insertion.sort(a); ??????? //exercise2.1.24 ??????? if(alg.equals("Insertion2")) Insertion2.sort(a); ??????? //exercise2.1.25 ??????? if(alg.equals("Insertion3")) Insertion3.sort(a); ??????? //exercise2.1.26 ??????? if(alg.equals("Insertion4")) Insertion3.sort(a); ??????? if(alg.equals("Selection")) Selection.sort(a); ??????? if(alg.equals("Shell")) Shell.sort(a); ?????? // if(alg.equals("Merge")) Merge.sort(a); ????? //? if(alg.equals("Quick")) Quick.sort(a); ????? //? if(alg.equals("Heap")) Heap.sort(a); ??????? return timer.elapsedTime(); ??? } ??? ??? public static double timeRandomInput(String alg,int N,int T) ??? { ??????? double total =0.0; ??????? Double[] a=new Double[N]; ??????? for (int t=0;t<T;t++) ??????? { ??????????? for (int i=0;i<N;i++) ??????????????? a[i]=StdRandom.uniform(); ??????????? total+=time(alg,a); ??????? } ??????? return total; ??? }//end timeRandomInput ??? ??? ??? public static void main(String[] args) ??? { ??????? /* ??????? String alg1=args[0]; ??????? String alg2=args[1]; ??????? int N=Integer.parseInt(args[2]); ??????? int T=Integer.parseInt(args[3]); ??????? double t1=timeRandomInput(alg1,N,T); ??????? double t2=timeRandomInput(alg2,T); ??????? StdOut.printf("For %d random Doublesn %s is",alg1); ??????? StdOut.printf(" %.2f times faster than %sn",t2/t1,alg2); ??????? */ ??????? double prevT1=0.0; ??????? double prevT2=0.0; ??????? double prevT3=0.0; ??????? double thisT1=0.0; ??????? double thisT2=0.0; ??????? double thisT3=0.0; ??????? for (int i=128;i<1000000;i=2*i) ??????? { ???????? prevT1=thisT1; ???????? prevT2=thisT2; ???????? prevT3=thisT3; ????????? // ???????? thisT1=timeRandomInput("Insertion",i,1); ???????? thisT2=timeRandomInput("Selection",1); ???????? thisT3=timeRandomInput("Shell",1); ???????? // ??????? StdOut.printf("---For %d random Doublesn",i); ??????? StdOut.printf("Insertion use time=%.2f,tihisTime/prevTime=%.2fn",thisT1,thisT1/prevT1); ??????? StdOut.printf("Selection use time=%.2f,thisT2,thisT2/prevT2); ??????? StdOut.printf("Shell???? use time=%.2f,thisT3,thisT3/prevT3); ??????? } ??? } ??? } public class Insertion { ??? public static void sort(Comparable[] a) ??? { ??????? int N=a.length; ??????? for (int i=0;i<N;i++) ??????? { ??????????? for(int j=i;j>0 && less(a[j],a[j-1]);j--) ??????????????? exch(a,j,j-1); ??????? } ??? } ??? ??? private static boolean less(Comparable v,Comparable w) ??? { return v.compareTo(w)<0;} ??? ??? private static void exch(Comparable[] a,int i,int j) ??? { ??????? Comparable t=a[i]; ??????? a[i]=a[j]; ??????? a[j]=t; ??? } ??? ??? private static void show(Comparable[] a) ??? { ??????? for (int i=0;i<a.length;i++) ??????????? StdOut.print(a[i]+" "); ??????? StdOut.println(); ??? } ??? ??? public static boolean isSorted(Comparable[] a) ??? { ??????? for (int i=0;i<a.length;i++) ??????????? if(less(a[i],a[i-1])) return false; ??????? return true; ??? } ??? ???? public static void main(String[] args) ??? { ??????? int N=Integer.parseInt(args[0]); ??????? Double[] a=new Double[N]; ??????? for(int i=0;i<N;i++) ??????????? a[i]=StdRandom.uniform(0.0,N*1.0); ??????? // ??????? sort(a); ??? } } public class Selection { ??? public static void sort(Comparable[] a) ??? { ??????? int N=a.length; ??????? for (int i=0;i<N;i++) ??????? { ??????????? int min=i; ??????????? for (int j=i+1;j<N;j++) ??????????????? if (less(a[j],a[min])) min=j; ??????????? exch(a,min); ??????????? //showAnimation(a); ??????? } ??? } ??? ??? private static boolean less(Comparable v,int j) ??? { ??????? Comparable t=a[i]; ??????? a[i]=a[j]; ??????? a[j]=t; ??? } ??? ??? private static void show(Comparable[] a) ??? { ??????? for (int i=0;i<a.length;i++) ??????????? StdOut.print(a[i]+" "); ??????? StdOut.println(); ??? } ??? ??? ??? private static void showAnimation(Comparable[] a) ??? { ?????? StdDraw.setXscale(0.0,a.length); ?????? StdDraw.setYscale(0.0,a.length); ?????? StdDraw.setPenRadius(0.005); ?????? StdDraw.pause(100); ?????? StdDraw.clear(StdDraw.GRAY); ?????? StdDraw.setPenColor(StdDraw.BLACK); ??????? for(int i=0;i<a.length;i++) ??????? { ??????????? StdDraw.line(i*1.0,0.0,i*1.0,(Double)a[i]*1.0); ??????? } ??? } ??? public static boolean isSorted(Comparable[] a) ??? { ??????? for (int i=0;i<a.length;i++) ??????????? if(less(a[i],a[i-1])) return false; ??????? return true; ??? } ??? ??? public static void main(String[] args) ??? { ??????? int N=Integer.parseInt(args[0]); ??????? Double[] a=new Double[N]; ??????? for(int i=0;i<N;i++) ??????????? a[i]=StdRandom.uniform(0.0,N*1.0); ??????? // ??????? StdDraw.pause(5000); ??????? sort(a); ??? } } public class Shell { ??? public static int timesOfCompare; ??? public static int timesOfCompareTotal; ??? public static void sort(Comparable[] a) ??? { ??????? int N=a.length; ??????? int h=1; ??????? while (h<N/3) h=3*h+1; ??????? while (h>=1) ??????? { ??????????? for (int i=h;i<N;i++) ??????????? { ???????????? for (int j=i;j>=h && less(a[j],a[j-h]);j-=h) ???????????? {? ???????????????? timesOfCompare++; ???????????????? exch(a,j-h); ???????????? } ??????????? } ????????? /* if (h>1) ???????? { ??????????? StdOut.printf("nsort-%dn",h); ??????????????????????? for(int l=0;l<N;l++) ??????????????????????? { ??????????????????????????? if (l%h==0) StdOut.println(); ??????????????????????????? StdOut.printf("%3d",a[l]); ??????????????????????? } ?????????? } ?????????? */ ??????????? h=h/3; ??????? } ??? } ??? //sort40 ??? public static void sort40(Comparable[] a) ??? { ??????? int N=a.length; ??????? int h=40; ??????? for (int i=h;i<N;i++) ??????????? { ????????????? for (int j=i;j>=h;j-=h) ?????????????????? {? ???????????????????? timesOfCompare++; ???????????????????? timesOfCompareTotal++; ??????????????????? // StdOut.printf("timesOfCompare=%d,i=%d,j=%d,j-h=%d n",timesOfCompare,j-h); ???????????????????? if (less(a[j],a[j-h]))? ???????????????????????? exch(a,j-h); ???????????????????? else ???????????????????????? break; ?????????????????? } ??????????? } ?????? ??????? /* StdOut.printf("nsort-%dn",h); ???????? for(int l=0;l<N;l++) ????????????? { ??????????????? if (l%h==0) StdOut.println(); ??????????????? StdOut.printf("%3d",a[l]); ????????????? } ????????? */ ??? } ??? //sort13 ??? public static void sort13(Comparable[] a) ??? { ??????? int N=a.length; ??????? int h=13; ??????? for (int i=h;i<N;i++) ??????????? { ????????????? for (int j=i;j>=h;j-=h) ?????????????????? {? ???????????????????? timesOfCompare++; ???????????????????? timesOfCompareTotal++; ???????????????????? if (less(a[j],j-h); ???????????????????? else ???????????????????????? break; ?????????????????? } ??????????? } ??????? /* ??????? StdOut.printf("nsort-%dn",a[l]); ????????????? } ????????????? */ ??? } ??? //sort4 ??? public static void sort4(Comparable[] a) ??? { ??????? int N=a.length; ??????? int h=4; ??????? for (int i=h;i<N;i++) ??????????? { ????????????? for (int j=i;j>=h;j-=h) ?????????????????? {? ???????????????????? timesOfCompare++; ???????????????????? timesOfCompareTotal++; ???????????????????? if (less(a[j],a[j-h])) ???????????????????????? exch(a,a[l]); ????????????? } ????????????? */ ??? } ??? //sort1 ??? public static void sort1(Comparable[] a) ??? { ??????? int N=a.length; ??????? int h=1; ??????? for (int i=h;i<N;i++) ??????????? { ????????????? for (int j=i;j>=h;j-=h) ?????????????????? {? ???????????????????? timesOfCompare++; ???????????????????? timesOfCompareTotal++; ???????????????????? if (less(a[j],a[l]); ????????????? } ????????????? */ ??? } ????? ??? ??? private static boolean less(Comparable v,Comparable w) ??? { ??????? return v.compareTo(w)<0; ??? } ??? ??? private static void exch(Comparable[] a,a[i-1])) return false; ??????? return true; ??? } ??? ??? public static void main(String[] args) ??? { ??? ??????? //worst sort13 ??????? Integer[] worst13={100,92,84,76,68,60,52,44,36,28,21,14,7,99,91,83,75,67,59,51,43,35,27,20,13,6,98,90,82,74,66,58,50,42,34,26,19,12,5,97,89,81,73,65,57,49,41,33,25,18,11,4,96,88,80,72,64,56,48,40,32,24,17,10,3,95,87,79,71,63,55,47,39,31,23,16,9,2,94,86,78,70,62,54,46,38,30,22,15,8,1,93,85,77,69,61,53,45,37,29}; ??????? timesOfCompareTotal=0; ??????? timesOfCompare=0; ??????? sort40(worst13); ??????? StdOut.printf("worst13 sort40 timesOfCompare=%4d timesOfCompareTotal=%4dn",timesOfCompareTotal); ?????? timesOfCompare=0; ?????? sort13(worst13); ?????? StdOut.printf("worst13 sort13 timesOfCompare=%4d timesOfCompareTotal=%4dn",timesOfCompareTotal); ?????? ??????? timesOfCompare=0; ??????? sort4(worst13); ??????? StdOut.printf("worst13? sort4 timesOfCompare=%4d timesOfCompareTotal=%4dn",timesOfCompareTotal); ?????? ??????? timesOfCompare=0; ??????? sort1(worst13); ??????? StdOut.printf("worst13? sort1 timesOfCompare=%4d timesOfCompareTotal=%4dn",timesOfCompareTotal); ??????? StdOut.println("------------------------------"); ?????????? ????? ??????? String[] files={ ??????????? "a40-13-4.txt","a40-4-13.txt","a13-4-40.txt","a13-40-4.txt","a4-40-13.txt","a4-13-40.txt",??????????? "b40-13-4.txt","b40-4-13.txt","b13-4-40.txt","b13-40-4.txt","b4-40-13.txt","b4-13-40.txt",??????????? "c40-13-4.txt","c40-4-13.txt","c13-4-40.txt","c13-40-4.txt","c4-40-13.txt","c4-13-40.txt",??????????? "d-big-small.txt","asc.txt" ??????? }; ??????? for(int f=0;f<files.length;f++) ??????? { ??????? int[] a=In.readInts(files[f]); ??????? Integer[] worst=new Integer[a.length]; ??????? for(int i=0;i<a.length;i++) ??????????? worst[i]=a[i]; ??????? timesOfCompareTotal=0; ??????? timesOfCompare=0; ??????? sort40(worst); ??????? StdOut.println("---"+files[f]+"---"); ??????? StdOut.printf("sort40 timesOfCompare=%4d timesOfCompareTotal=%4dn",timesOfCompareTotal); ??????? timesOfCompare=0; ??????? sort13(worst); ??????? StdOut.printf("sort13 timesOfCompare=%4d timesOfCompareTotal=%4dn",timesOfCompareTotal); ?????? ??????? timesOfCompare=0; ??????? sort4(worst); ??????? StdOut.printf("sort4 timesOfCompare=%4d timesOfCompareTotal=%4dn",timesOfCompareTotal); ?????? ??????? timesOfCompare=0; ??????? sort1(worst); ??????? StdOut.printf("sort1 timesOfCompare=%4d timesOfCompareTotal=%4dn",timesOfCompareTotal); ??????? StdOut.println(""); ??????? } ??? }???? ?? }
