把<0的也算入大小为0的数组
通过统计可以得出，他们的大小是与N存在一定比例的关系
package Cap2_3;import Cap2_1.SortTemplate;
import edu.princeton.cs.introcs.StdOut;
import edu.princeton.cs.introcs.StdRandom;public class Quick extends SortTemplate{private static int[] cnt = new int[3];public static void sort(Comparable[] a){StdRandom.shuffle(a);sort(a, 0, a.length-1);}private static void sort(Comparable[] a, int lo, int hi){if(hi-lo<=2){cnt[hi-lo<0?0:hi-lo]++;}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(j>i) exch(a, i, j);else break;}exch(a, lo, j);return j;}public static void main(String[] args) {// TODO Auto-generated method stubfor(int N=10;N<=100000;N*=10){for(int i=0;i<3;i++)Quick.cnt[i]=0;Integer[] a = new Integer[N];for(int i=0;i<N;i++)a[i]=i;StdRandom.shuffle(a);sort(a);assert isSorted(a);StdOut.println("N="+N+" \tcnt[0]="+Quick.cnt[0]+"\tcnt[1]="+Quick.cnt[1]+"\tcnt[2]="+Quick.cnt[2]);}}}
N=10 cnt[0]=7 cnt[1]=2 cnt[2]=0
N=100 cnt[0]=65 cnt[1]=16 cnt[2]=13
N=1000 cnt[0]=676 cnt[1]=164 cnt[2]=99
N=10000 cnt[0]=6650 cnt[1]=1644 cnt[2]=1002
N=100000 cnt[0]=66636 cnt[1]=16645 cnt[2]=9938