import java.util.Arrays;
import java.util.Collections;
import java.util.List;
public class QuickSort> extends Sort {
@Override
public void sort(T[] nums) {
shuffle(nums);
sort(nums, 0, nums.length - 1);
}
protected void sort(T[] nums, int l, int h) {
if (h <= l) {
return;
}
int j = partition(nums, l, h);
sort(nums, l, j - 1);
sort(nums, j + 1, h);
}
private void shuffle(T[] nums) {
List list = Arrays.asList(nums);
Collections.shuffle(list);
list.toArray(nums);
}
private int partition(T[] nums, int l, int h) {
int i = l, j = h + 1;
T v = nums[l];
while (true) {
while (less(nums[++i], v) && i != h) ;
while (less(v, nums[--j]) && j != l) ;
if (i >= j) {
break;
}
swap(nums, i, j);
}
swap(nums, l, j);
return j;
}
public T select(T[] nums, int k) {
int l = 0, h = nums.length - 1;
while (h > l) {
int j = partition(nums, l, h);
if (j == k) {
return nums[k];
} else if (j > k) {
h = j - 1;
} else {
l = j + 1;
}
}
return nums[k];
}
public static void main(String[] args) {
QuickSort sort = new QuickSort();
Integer[] nums = {3, 1, 6, 2, 5, 8, 4, 7};
sort.partition(nums, 0, 7);
}
}