2.3.25切换到插入排序。实现一个快速排序，在子数组元素少于M时切换到插入排序。用快速排序处理大小N分别为10^3、10^4、10^5和10^6的随机数组，根据经验给出使其在你的计算环境中运行速度最快的M值。将M从0变化到30的每个值所得到的平均运行时间绘成曲线。注意：你需要为算法2.2添加一个需要三个参数的sort()方法以使Insertion.sort(a,lo,hi)将子数组a[lo..hi]排序。

答：

1）使用10^6长度的数组，M从2到99,进行了100次测试，排序用时最少的M在6至25之间，其中M=11时，排序用时最少的次数出现最多。具体有：M=11时 15次用时最少，M=15时 12次用时最少，M=13时 12次用时最少,M=10时 11次用时最少。

2)见图

import java.awt.Color;

public class E2d3d25

{

    public static void sort(Comparable[] a,int M)

    {

      //StdRandom.shuffle(a);

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

    }

   

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

    {

        //数组少于等于M个元素时使用插入排序

        if (hi-lo+1<M)

        {

            InsertSort(a,lo,hi);

            return;

        }

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

   

        sort(a,lo,j-1,M);

        sort(a,j+1,hi,M);

    }

 

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

    {

        int i=lo,j=hi+1;

        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 void InsertSort(Comparable[] a,int lo,int hi)

    {

        for (int i=lo+1;i<hi+1;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=1;i<a.length;i++)

            if(less(a[i],a[i-1])) return false;

        return true;

    }

    public static void bestM()

    {

        //用来记录M不同值时排序花费的时间

        Double[] T=new Double[100];

        //使用一个10^6方的数组进行排序测试

        int N=1000000;

        Double[] a=new Double[N];

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

            a[i]=StdRandom.random();

        //子数组最小长度只可能是1,所以M必须从1开始

        //跳过为0、1的索引使得索引与M一一直接对应

        for(int M=2;M<T.length;M++)

        {

            //对于不同的M使用相同的排列进行排序

            Double[] aClone=new Double[a.length];

            for(int i=0;i<a.length;i++)

                aClone[i]=a[i];

            //开始排序并计时

             Stopwatch timer=new Stopwatch();

             sort(aClone,M);

             T[M]=timer.elapsedTime();

             //StdOut.printf("%d\t%f\n",M,T[M]);

        }//end for M

        //找出用时最小的M

        int minM=2;

        for(int i=3;i<T.length;i++)

            if (less(T[i],T[minM])) minM=i;

        StdOut.println("best M=" +minM);       

    }//end bestM

 

    public static void drawAverageTime()

    {

        //

        StdDraw.setXscale(0,35);

        StdDraw.setYscale(-0.5,3);

        //

        int Nlen[]={100000,1000000,3000000};//

        for(int Ni=0;Ni<Nlen.length;Ni++)

        {

          int N=Nlen[Ni];

          //生成一个长度为N的数组a

          Double[] a=new Double[N];

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

            a[i]=StdRandom.random(); 

          //M从0至30对数对组a的副本进行排序,同一长度的N,不同的M时待排序数组内容相同

          Double totalTime=0.0;

          StdDraw.setPenColor(Color.BLACK);

          StdDraw.setPenRadius(0.02);

          for(int M=2;M<=30;M++)

          {

              //生成一个数组a的副本aClone

              Double[] aClone=new Double[N];

              for (int i=0;i<a.length;i++)

                  aClone[i]=a[i];

              //数组长度为N,小于等于M时切换到插入排序的快速排序

              Stopwatch timer=new Stopwatch();

              sort(aClone,M);

              totalTime=totalTime+timer.elapsedTime();

              StdDraw.point(M,timer.elapsedTime());

          }//end for M

          StdDraw.setPenColor(Color.RED);

          StdDraw.setPenRadius(0.01);

          StdDraw.line(2,totalTime/29,30,totalTime/29);

        }//end for Ni

    }

  

    public static void main(String[] args)

    {

        //for (int i=0;i<100;i++)

        //   bestM();

        drawAverageTime();

      

    }//end main

}//end class