package sort;

public class QuickSort {

public static void Sort(int[] a, int l, int r){ //快速排序

int x = a[l + ((r - l)>>1)];

int i = l;

int j = r;

while(i<=j){

while(a[i] < x) i++;

while(x < a[j]) j--;

if(i<=j){

int temp = a[i];

a[i] = a[j];

a[j] = temp;

i++;

j--;

}

}

if(l<j) Sort(a, l, j);

if(i<r) Sort(a, i, r);

}

public static int select(int[] a, int l, int r, int k){ //快速选择

int x = a[l + ((r - l)>>1)];

int i = l;

int j = r;

while(i<=j){

while(a[i] < x) i++;

while(x < a[j]) j--;

if(i<=j){

int temp = a[i];

a[i] = a[j];

a[j]= temp;

i++;

j--;

}

}

if((l<j)&&(k<=j)) return select(a,l,j,k);

else if((i<r)&&(i<=k)) return select(a,i,r,k);

else return a[k];

}

public static void main(String[] args) {

int[] a = new int[]{2,3,4,8,6,7,2,10,2,3,4,5,67,3,4,6,4,7,5,3,23,4,5,6,4,2};

Sort(a,0,a.length-1);

for(int i:a){

System.out.print(i+" ");

}

System.out.println();

System.out.println(select(a,0,a.length-1,2));

}

}