Algs4-2.3.26子数组大小直方图

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