速排改善版——3分9分ダブルポインタ総合版を挿入


ブロガーは他の人のブログとArraysを見ています.sort()まとめた速排改善版
public class QucikSort {

	public static void main(String[] args) {
		//int a[]={9,8,6,1,2,5,4,8,3,7,1,2,0,15,12,11,13,18,9,7,5,6,4,12,17,20};
		int a[]={20,19,18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1,0};
		quickSort(a,0,a.length-1);
		output(a);

	}
	private static void output(int[] a) {
		for(int val:a)
			System.out.print(val+" ");
		
	}
	public static void quickSort(int[] a,int left,int right){
		if(a.length==0||left<0||right<0||left>right)
			return;
		int len=right-left+1;
		
		if(len<7){
			for(int i=left;i<=right;i++){
				int temp=a[i]; 
				int j=i-1;
				for(;j>=left&&a[j]>=temp;j--)
					a[j+1]=a[j];
				a[j+1]=temp;
			}
			return ;
		}
		int l=left;
		int m=left+len>>1;
		int n=left+len-1;
		int s=len/8;
		if(len>40){
			
			l = med3(a, l, l + s, l + 2 * s); //  3 
            m = med3(a, m - s, m, m + s); //  3 
            n = med3(a, n - 2 * s, n - s, n); //  3 
		}
		m = med3(a, l, m, n);
		swap(a,left,m);
		
		int x=a[left];
		int i=left;
		int j=right;
		while(i=x) j--;
			if(i x[c] ? b : x[a] > x[c] ? c : a;
    }
}