参考文档
= https://blog.csdn.net/nrsc272420199/article/details/82587933
public static void main(String[] args) {
int[] arr = { 49, 38, 65, 97, 23, 22, 76, 1, 5, 8, 2, 0, -1, 22 };
// 第一次进入的时候分别指向数组的最左边和最右边
int left = 0, right = arr.length - 1;
quickSort(arr, left, right);
System.out.println("排序后:");
Arrays.stream(arr).forEach(i -> {
System.out.print(i+", ");
});
}
private static void quickSort(int[] arr, int left, int right) {
if (left < right) {
// 寻找 基准 数据的正确索引
int mid = getIndex(arr, left, right);
// 进行迭代对index之前和之后的数组进行相同的操作使整个数组变成有序
// 对 left 到 基准(mid) 数据的前一个的那半部分 , 即 left ... mid-1 进行排序
quickSort(arr, left, mid - 1);
// 对 基准(mid)的后一个 到 right 的那半部分 , 即 mid+1 ... right 进行排序
quickSort(arr, mid + 1, right);
}
}
private static int getIndex(int[] arr, int left, int right) {
// 基准数据
int tmp = arr[left];
while (left < right) {
// 当队尾(最右边)的元素(arr[right]) 大于等于 基准数据时, 向前(向左)移动 right 指针
while (left < right && arr[right] >= tmp) {
right--;
}
// 如果队尾(最右边)元素小于tmp了,需要将其赋值给left(最左边)
arr[left] = arr[right];
// 当队首(最左边)元素(arr[left])小于等于tmp时,向前(向右)移动 left 指针
while (left < right && arr[left] <= tmp) {
left++;
}
// 当队首(最左边)元素大于tmp时,需要将其赋值给right(最右边)
arr[right] = arr[left];
}
// 跳出循环时left和right相等,此时的left或right都是tmp的正确索引位置
// 可以知道left或right位置的值并不是tmp,所以需要将tmp赋值给arr[left]或者arr[right]
arr[left] = tmp; // 等价于 arr[right] = tmp;
return left; // 返回tmp的正确位置 或者 return right;
}