参考:https://segmentfault.com/a/1190000040022056
- 双指针交换法;
- pivot选取初始点;
从后往前找小;从前往后找大;分别交换,目的:小在左,大在右。
public void quickSort(int[] arr, int start, int end) {
if(start >= end) {
return;
}
int idx = randomizedPartition(arr, start, end);
quickSort(arr, start, idx-1);
quickSort(arr, idx+1, end);
}
private int randomizedPartition (int[] arr, int start, int end) {
int i = new Random().nexInt(end-start+1) + start;
swap(arr, i, end);
return partition(arr, start, end);
}
private int partition (int[] arr, int start, int end) {
int pivot = arr[end];
int idx = start;
for(int i=start; i<end; i++) {
if(arr[i] < pivot) {
swap(arr, i, idx++);
}
}
swap(arr, idx, end);
return idx;
}