You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
40 lines
820 B
40 lines
820 B
package sort;
|
|
|
|
|
|
public class QuickSort {
|
|
|
|
private static void exch(int[] a,int i,int j){
|
|
int t=a[i];
|
|
a[i]=a[j];
|
|
a[j]=t;
|
|
}
|
|
|
|
private static int partition(int[] a,int lo,int hi){
|
|
int i=lo,j=hi+1;
|
|
int v=a[lo];
|
|
while(true){
|
|
while(a[++i]<v)
|
|
if(i==hi)
|
|
break;
|
|
while(a[--j]>v)
|
|
if(j==lo)
|
|
break;
|
|
if(i>=j)
|
|
break;
|
|
exch(a,i,j);
|
|
}
|
|
exch(a,lo,j);
|
|
return j;
|
|
}
|
|
private static void sort(int[] a, int lo,int hi){
|
|
if(hi<=lo)
|
|
return;
|
|
int j=partition(a,lo,hi);
|
|
sort(a,lo,j-1);
|
|
sort(a,j+1,hi);
|
|
}
|
|
public void sort(int[] a){
|
|
sort(a,0,a.length-1);
|
|
}
|
|
}
|