2.3.7在使用快速排序将N个不重复的元素排序时,计算大小为0、1和2的子数组的数量。如果你喜欢数学，请推导;如果你不喜欢，请做一些实验并提出猜想。

答：设使用快速排序的数组长度为N。

将数组一分为二时之前的分界元素不在这两个子数组中，所以两个子数组的总长度为N-1。

归纳得出第i层的所有子数组中的元素总个数为第i-1层元素总个数-第i-1层的节点数，得出第i层所有子数据的元素总数a=N-2^0-2^1-2^3...-2^(i-1)=N-(2^0+2^1+2^2+2^3+...2^(i-1))=N-(2^i-1)=N-2^i+1

由二叉树性质得出第i层的节点个数b=2^i

第i层各节点的平均拥有的元素个数c=a/b,代入得c=(N-2^i+1)/2^i

c=(N+1)/2^i-2^i/2^i

c=(N+1)/2^i-1

(N+1)/2^i=c+1

2^i=(N+1)/(c+1)

据此得大小为0的子数组个数<=N+1个，大小为1的子数组个数<=(N+1)/2 ，大小为2的子数组个数<=(N+2)/3

实验数据表示 子数组个数介于 (N+1)/(c+1)/2 与(N+1)/(c+1)之间。

实验数据如下图：

代码如下：

public class E2d3d7

{

    static int array0=0;

    static int array1=0;

    static int array2=0;

    public static void sort(Comparable[] a)

    {

           array0=0;

      array1=0;

      array2=0;

   

      int N=a.length;

      StdRandom.shuffle(a);

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

      StdOut.printf("N=%7d array0=%7d array1=%7d array2=%7d\n",a.length,array0,array1,array2);

    }

   

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

    {

        if (hi-lo+1==0)

            array0++;

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

            array1++;

        else if(hi-lo+1==2)

            array2++;

       

        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;

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

    {

        Double[] a=new Double[100];

        Double[] b=new Double[1000];

        Double[] c=new Double[10000];

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

            a[i]=StdRandom.uniform();

       

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

            b[i]=StdRandom.uniform();

       

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

            c[i]=StdRandom.uniform();

       

        sort(a);

        sort(b);

        sort(c);

    }

}