import java.util.Arrays;
class Main {
public static void main(String[] args) {
int[] arr = {6, 1, 2, 7, 9, 3, 4, 5, 10, 8};
quickSort(arr, 0, arr.length - 1);
System.out.println(Arrays.toString(arr));
}
/**
* @param arr
* @param left 左边界
* @param right 右边界
*/
private static void quickSort(int[] arr, int left, int right) {
//排序结束
if (left >= right)
return ;
//获取中间位置的索引
int pivotIndex = partition(arr, left, right);
//左边递归
quickSort(arr, left, pivotIndex - 1);
//右边递归
quickSort(arr, pivotIndex + 1, right);
}
//寻找中轴位置
private static int partition(int[] arr, int left, int right) {
//以第一个元素为中轴
int pivot = arr[left];
while (left < right) {
//如果arr[right]大于中轴的值，right向左移动，当arr[right]小于中轴值得时候
while (left < right && arr[right] >= pivot)
right--;
//将这个较小的值赋给头元素，即完成了小于中轴的放在中轴的左边，
//且left右移一位，减少下面的一次比较次数
if (left < right)
arr[left++] = arr[right];
//如果arr[left]小于中轴的值，left向右移动，当arr[left]大于中轴值得时候
while (left < right && arr[left] <= pivot)
left++;
//将这个较大的值赋给arr[right]，即完成了大于中轴的放在中轴的右边
if (left < right)
arr[right--] = arr[left];
}
//left最终时中轴位置,将中轴值赋给中轴的位置
arr[left] = pivot;
return left;
}
}
