2.3.19五取样切分。实现一种基于随机抽取子数组中5个元素并取中位数进行切分的快速排序。将取样元素放在数组的一侧以保证只有中位数元素参与了切分。运行双倍测试来确定这样改动的效果，并和标准的快速排序以及三取样切分的快速排序(请见上一道练习)进行比较。附加题：找到一种对于任意输入都只需要少于7次比较的五取样算法。

public class E2d3d19

{

    public static void sort(Comparable[] a)

    {

      StdRandom.shuffle(a);

      sort(a,0,a.length-1);

    }

   

    private static void sort(Comparable[] a,int lo,int hi)

    {

        if (hi<=lo) return;

        int j=partition(a,lo,hi);

   

        sort(a,lo,j-1);

        sort(a,j+1,hi);

    }

 

    private static int partition(Comparable[] a,int lo,int hi)

    {

        int i=lo,j=hi+1;

        int newVIndex=FiveMedianIndex(a,lo,hi);

        exch(a,lo,newVIndex);

        Comparable v=a[lo];

        while(true)

        {

            while(less(a[++i],v)) if(i==hi) break;

            while(less(v,a[--j])) if(j==lo) break;

          

            if(i>=j) break;

            exch(a,i,j);

        }

        exch(a,lo,j);

        return j;

    }

    //返回五取样切分元素索引

    private static int FiveMedianIndex(Comparable[] a,int lo,int hi)

    {

        //子数组少于5个元素时，第一个元素作为切分元素

        if((hi-lo+1)<5)  return lo;

        Integer[] b ;

        b=new Integer[5];

        //子数组有5个元素时，取这5个元素的中位数作为切分元素

        if ((hi-lo+1)==5)

        {

            b[0]=lo;

            b[1]=lo+1;

            b[2]=lo+2;

            b[3]=lo+3;

            b[4]=lo+4;

        }

        //子数组有5个以上的元素时，随机取5个元素的索引作为新数组的值，然后找中位数所在的索引

        if((hi-lo+1)>5) 

        {

            b[0]=StdRandom.uniform(lo,hi+1);

            b[1]=StdRandom.uniform(lo,hi+1);

            b[2]=StdRandom.uniform(lo,hi+1);

            b[3]=StdRandom.uniform(lo,hi+1);

            b[4]=StdRandom.uniform(lo,hi+1);

        }

       使用插入排序法排序新数组b,按原数组的值进行排序。排序后的结果是原数组中小中大值对应的索引

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

            for(int j=i+1;j>0;j--)

               if (less(a[b[j]],a[b[j-1]])) exch(b,j,j-1);

        return b[2];

    }

    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=1;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 k=0;k<N;k++)

            a[k]=StdRandom.random();

     

          sort(a);

        assert  isSorted(a);

        show(a);

    }

}

--双倍测试

public class DoublingTest

{

    public static double timeTrial(int N)

    {

        int MAX=1000000;

        Integer[] a=new Integer[N];

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

            a[i]=StdRandom.uniform(-MAX,MAX);

        Stopwatch timer=new Stopwatch();

        E2d3d19.sort(a);

        //Quick.sort(a);

        return timer.elapsedTime();

    }

   

    public static void main(String[] args)

    {

        for(int N=250;true;N=N+N)

        {

            double time=timeTrial(N);

            StdOut.printf("%7d %5.1f\n",N,time);

        }

    }

}