2.3.26子数组大小。编写一个程序，在快速排序处理大小为N的数组的过程中，当子数组的大小小于M时，排序方法需要切换为插入排序。将子数组的大小绘制成直方图。用N=10^5,M=10、20和50测试你的程序。

M=10时

M=20时

M=50时

import java.awt.Color;

public class E2d3d26

{

    public static int[] subArray;

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

    {

      //StdRandom.shuffle(a);

      subArray=new int[M];

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

      //

      StdDraw.setXscale(-2,M+2);

      StdDraw.setYscale(0,a.length/M/4);

      StdDraw.setPenRadius(0.01);

      StdDraw.setPenColor(Color.RED);

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

          StdDraw.filledRectangle(1.0*i,0.0,0.2,subArray[i]);

    }

   

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

    {

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

        if (hi-lo+1<M)

        {

            subArray[hi-lo+1]=subArray[hi-lo+1]+1;

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

    {

          int N=100000;

          int M=Integer.parseInt(args[0]);

          Double[] a=new Double[N];

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

            a[i]=StdRandom.random(); 

         //

          sort(a,M);

    }//end main

}//end class