2.1.37部分有序。編寫一個測試用例 ，生成部分有序的數組，包括：
1)95%有序，其余部分為隨機值;
2)所有元素和它們的正確位置的距離都不超過10;
3)5%的元素隨機分布在整個數組中，剩下的數據都是有序的。
評估并驗證這些輸入數據對本節討論的算法的性能的影響。
插入排序在左邊有序，右邊隨機的情況下排序性能最差，其他情況下性能較好。
選擇排序在所有情況下性能都較差。
希爾排序對所有情況性能都比較好，在左邊95%有序時性能略差。

import java.util.Arrays;
public class E2d1d37
{
??? public static double time (String alg,Double[] a)
??? {
??????? Stopwatch timer =new Stopwatch();
??????? if(alg.equals("Insertion")) Insertion.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,int probabilityTYPE)
??? {
??????? double total =0.0;
??????? Double[] a=new Double[N];

??????? if (probabilityTYPE==0)
??????? {
??????????? for (int t=0;t<T;t++)
??????????? {
??????????????? LeftRandom95sorted(a);
??????????????? total+=time(alg,a);
??????????? }
??????? }
??????? //probabilityTYPE=1 Poisson distribution
??????? if (probabilityTYPE==1)
??????? {
??????????? for (int t=0;t<T;t++)
??????????? {
??????????????? RightRandom95sorted(a);
??????????????? total+=time(alg,a);
??????????? }
??????? }
??????? //probabilityTYPE=2 Geometric distribution
??????? if (probabilityTYPE==2)
??????? {
??????????? for (int t=0;t<T;t++)
??????????? {
??????????????? uniform5Random95sorted(a);
??????????????? total+=time(alg,a);
??????????? }
??????? }
???????? //probabilityTYPE=3 Geometric distribution
??????? if (probabilityTYPE==3)
??????? {
??????????? for (int t=0;t<T;t++)
??????????? {
??????????????? distance10(a);
??????????????? total+=time(alg,a);
??????????? }
??????? }
?????? return total;
??? }//end timeRandomInput

??? public static void LeftRandom95sorted(Double[] a)
??? {
??????? for (int i=0;i<a.length;i++)
???????????? a[i]=StdRandom.uniform();
??????? Arrays.sort(a);
??????? int rate5=(int)0.05*a.length;
??????? for(int i=0;i<rate5;i++)
???????????? a[i]=StdRandom.uniform();
??? }
???
????? public static void RightRandom95sorted(Double[] a)
??? {
???????
??????? for (int i=0;i<a.length;i++)
???????????? a[i]=StdRandom.uniform();
??????? Arrays.sort(a);
??????? int rate95=(int)0.95*a.length;
??????? for(int i=rate95;i<a.length;i++)
???????????? a[i]=StdRandom.uniform();
??? }
????
???? public static void uniform5Random95sorted(Double[] a)
??? {
??????? for (int i=0;i<a.length;i++)
???????????? a[i]=StdRandom.uniform();
??????? Arrays.sort(a);
??????? int rate5=(int)0.05*a.length;
??????? for(int i=0;i<rate5;i++);
???????????? a[StdRandom.uniform(0,a.length)]=StdRandom.uniform();
??? }
???
??? public static void distance10(Double[] a)
??? {
??????? for (int i=0;i<a.length;i++)
???????????? a[i]=StdRandom.uniform();
??????? Arrays.sort(a);
??????? int distance=10;
??????? int postion;
??????? Double temp;
??????? for(int i=0;i<a.length-distance;i++)
??????? {
??????????? postion=StdRandom.uniform(i+1,i+distance+1);
??????????? temp=a[i];
??????????? a[i]=a[postion];
??????????? a[postion]=temp;
??????? }
???????
??????? for(int i=a.length-1;i>=a.length-distance;i--)
??????? {
??????????? postion=StdRandom.uniform(i-distance,a.length);
??????????? temp=a[i];
??????????? a[i]=a[postion];
??????????? a[postion]=temp;
??????? }
??? }???
???????
??? public static void main(String[] args)
??? {
?????
??????? Integer N=Integer.parseInt(args[0]);
??????? Integer T=Integer.parseInt(args[1]);
???????????????
??????? String[] CASEmem=new String[4];
??????? CASEmem[0]="LeftRandom95sorted";
??????? CASEmem[1]="95sortedRightRandom";
??????? CASEmem[2]="uniform5Random95sorted";
??????? CASEmem[3]="distance10";
???????


???????? Double time;
???????? StdOut.printf("---Insertion---\n");
????????? time=timeRandomInput("Insertion",N,T,0);
???????? StdOut.printf("For %d? double with case %25s,spend time=%.2f\n",N,CASEmem[0],time);
???????? time =timeRandomInput("Insertion",N,T,1);
???????? StdOut.printf("For %d? double with case %25s,spend time=%.2f\n",N,CASEmem[1],time);
???????? time =timeRandomInput("Insertion",N,T,2);
???????? StdOut.printf("For %d? double with case %25s,spend time=%.2f\n",N,CASEmem[2],time);
???????? time =timeRandomInput("Insertion",N,T,3);
???????? StdOut.printf("For %d? double with case %25s,spend time=%.2f\n",N,CASEmem[3],time);
???????
????????
???????? StdOut.printf("---Selection---\n");
???????? time =timeRandomInput("Selection",N,T,0);
???????? StdOut.printf("For %d? double with case %25s,spend time=%.2f\n",N,CASEmem[0],time);
???????? time =timeRandomInput("Selection",N,T,1);
???????? StdOut.printf("For %d? double with case %25s,spend time=%.2f\n",N,CASEmem[1],time);
???????? time =timeRandomInput("Selection",N,T,2);
???????? StdOut.printf("For %d? double with case %25s,spend time=%.2f\n",N,CASEmem[2],time);
???????? time =timeRandomInput("Selection",N,T,3);
???????? StdOut.printf("For %d? double with case %25s,spend time=%.2f\n",N,CASEmem[3],time);
????????
???????? StdOut.printf("---Shell---\n");
???????? time =timeRandomInput("Shell",N,T,0);
???????? StdOut.printf("For %d? double with case %25s,spend time=%.2f\n",N,CASEmem[0],time);
???????? time =timeRandomInput("Shell",N,T,1);
???????? StdOut.printf("For %d? double with case %25s,spend time=%.2f\n",N,CASEmem[1],time);
???????? time =timeRandomInput("Shell",N,T,2);
???????? StdOut.printf("For %d? double with case %25s,spend time=%.2f\n",N,CASEmem[2],time);
???????? time =timeRandomInput("Shell",N,T,3);
???????? StdOut.printf("For %d? double with case %25s,spend time=%.2f\n",N,CASEmem[2],time);

??? }
}

轉載于:https://www.cnblogs.com/longjin2018/p/9860069.html

總結

以上是生活随笔為你收集整理的Algs4-2.1.37部分有序的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。