算法 第四版 2.3.7

把<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 stub
		for(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