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);

    }

}