2.3.28递归深度。用经验性的研究估计切换阀值为M的快速排序在将大小为N的不重复数组排序时的平均递归深度，其中M=10、20和50，N=10^3、10^4、10^5和10^6。

答：通过测试数据得平均递归深度为2.679lg(N/M)

public class E2d3d28

{

   

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

    {

      //StdRandom.shuffle(a);

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

     

    }

   

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

    {

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

        if (hi-lo+1<M)

        {

            InsertSort(a,lo,hi);

            return 1;

        }

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

        int leftDepth=sort(a,lo,j-1,M);

        int rightDepth=sort(a,j+1,hi,M);

        if (leftDepth>rightDepth)

            return leftDepth+1;

        else

            return rightDepth+1;

    }

    

   

    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 main(String[] args)

    {

        int Nlen[]={1000,10000,100000,1000000};

        int Mlen[]={10,20,50};

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

        {

          int N=Nlen[Ni];

          for (int Mi=0;Mi<Mlen.length;Mi++)

          {

             int M=Mlen[Mi];

             int depth=0;

             for (int time=0;time<10;time++)

             {

                 Double[] a=new Double[N];

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

                     a[i]=StdRandom.random(); 

                  depth=depth+sort(a,M);

             }

             StdOut.printf("%d\t%d\t%d\n",N,M,depth/10);

          }

        }//end for Ni

    }//end main

}//end class