2.1.34罕见情况。编写一个测试用例，调用sort()方法对实际应用中可能出现困难或极端情况的数组进行排序。比如，数组可能已经有序的，或是逆序的，数组的所有主键相同，数组的主键只有两种值，大小为0或是1的数组。

从以下运行结果可以看出：

插入排序时：有序时用时会很少，反序时用时比随机排列和有序要多， 元素只有一个值时用时少，元素有两个值时比选择排序要少。0个和1个元素几乎不用时。

选择排序时：随机元素、有序、反序时排序用时没有明显区别，元素只有1个值，或只有两个值时排序时间比随机元素值时用时更多。0个和1个元素几乎不用时。

希尔排序：在多值元素随机排列、有序、反序、元素只有一个值、元素只有两个值、只有0个元素、只有一个元素时性能都会常好。反序排序比随机排列排序用时更短。

1)插入排序

2)选择排序

3)希尔排序

4)希尔排序一百万

import java.util.Arrays;

public class E2d1d34

{

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

    {

        double total =0.0;

        Double[] a=new Double[N];

        //CASE=0 random

        if (CASE==0)

        {

            for (int t=0;t<T;t++)

            {

                for (int i=0;i<N;i++)

                    a[i]=StdRandom.uniform();

                total+=time(alg,a);

            }

        }

        //CASE=1 asc sorted

         if (CASE==1)

        {

            for (int t=0;t<T;t++)

            {

                for (int i=0;i<N;i++)

                    a[i]=StdRandom.uniform();

                Arrays.sort(a);

                total+=time(alg,a);

            }

        }

         //CASE=2 desc sorted

         if (CASE==2)

        {

            for (int t=0;t<T;t++)

            {

                for (int i=0;i<N;i++)

                    a[i]=StdRandom.uniform();

                Arrays.sort(a);

                for(int i=0;i<=(a.length-1)/2;i++)

                {

                    Double temp=a[i];

                    a[i]=a[N-1-i];

                    a[N-1-i]=temp;

                }

                total+=time(alg,a);

            }

        }

        //CASE=3 one key value

         if (CASE==3)

        {

            for (int t=0;t<T;t++)

            {

                Double temp=StdRandom.uniform();

                for (int i=0;i<N;i++)

                    a[i]=temp;

                total+=time(alg,a);

            }

        }

         //CASE=4 two key value

         if (CASE==4)

        {

            for (int t=0;t<T;t++)

            {

                for (int i=0;i<N;i++)

                    a[i]=1.0*StdRandom.uniform(0,2);

                total+=time(alg,a);

            }

        }

        //CASE=5 array length 0

         if (CASE==5)

        {

             if (N>0)

             {

                 StdOut.println("Case 5,N must be 0.");

                 return -1.0;

             }

                

            for (int t=0;t<T;t++)

            {

                for (int i=0;i<N;i++)

                    a[i]=StdRandom.uniform();

                total+=time(alg,a);

            }

        }

         //CASE=6 array length 1

         if (CASE==6)

        {

             if (N!=1)

             {

                 StdOut.println("Case 6,N must be 1.");

                 return -2.0;

             }

                

            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 alg=args[0];

        Integer N=Integer.parseInt(args[1]);

        Integer CASE=Integer.parseInt(args[2]);

        //CASE =0  random

        //CASE =1  asc sorted

        //CASE =2  desc sorted

        //CASE =3  one key value

        //CASE =4  two key value

        //CASE =5  array length 0

        //CASE =6  array length 1

        String[] CASEmem=new String[7];

        CASEmem[0]="random";

        CASEmem[1]="asc sorted";

        CASEmem[2]="desc sorted";

        CASEmem[3]="one key value";

        CASEmem[4]="two key value";

        CASEmem[5]="array length 0";

        CASEmem[6]="array length 1";

         Double time =timeRandomInput(alg,N,1,CASE);

         StdOut.printf("For %d random double with case %s,spend time=%.2f\n",N,CASEmem[CASE],time);

    }

}