速排改善版——3分9分ダブルポインタ総合版を挿入
1332 ワード
ブロガーは他の人のブログと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;
}
}