基本思想
对于一组数据，选择一个基准元素（base），通常选择第一个或最后一个元素，通过一轮扫描，比base小的元素都在base左边，比base大的元素都在base右边，对左右子序列用相同的方法递归排序，直到序列中所有数据均有序为止。
快速排序，说白了就是给基准数据找其正确索引位置的过程。
思路图解
以 [19,97,09,17,01,08] 为例，以第一个元素19为base，定义左右两个指针 L和 R，分别从两端开始扫描。从右向左找比19小的数，替换L所在位置的元素。再从左往右找比19大的数，然后替换R所在位置的元素。重复此过程直至L和R重合（两个指针指向同一元素），base替换此元素，此时第一轮结束。再递归排序base左右两部分的元素。
首先R从后向前扫描，如果扫描到的值大于基准数据就让R减1，然后继续往前扫描，直到发现有元素比该基准数据的值小(如上图中08<=base)，就将R位置的值赋值给L位置 ,结果如下:
然后交替移动L下标：L从前往后扫描,如果扫描到的值小于基准数据就让L加1，然后继续向后扫描，直到发现有元素大于基准数据的值(如上图97>=base)，就再将L位置的值赋值给R位置的值,指针移动并且数据交换后的结果如下:
然后交替移动R下标，向前移动，直到扫描到小于基准数的值，如上图继续扫描到 01 <= 19，则就将R位置的值赋值给L位置 ,结果如下:
然后继续交替移动L下标，向后移动，如上图L一直向后扫描，09比基准数小，继续后移，17比基准数小，继续后移，这时候L和R重合，则base替换此元素。
左子序列都比19小，右子序列都比19大
然后对左右子序列重复以上操作即可。
代码实现
/**
* @ClassName QuickSort
* @author: shouanzh
* @Description 快速排序
* @date 2022/5/8 17:42
*/
public class QuickSort {
public static void main(String[] args) {
int[] array = new int[]{100, 89, 66, 1, -1, 30, 5, 85, -25};
quickSort(array, 0, array.length - 1);
System.out.println(Arrays.toString(array)); // [-25, -1, 1, 5, 30, 66, 85, 89, 100]
}
/**
* 快速排序
* @param arr 数组
* @param left 数组左边界
* @param right 数组右边界
*/
private static void quickSort(int[] arr, int left, int right) {
if (left < right) {
// 每次分割的点pos
int pos = partition(arr, left, right);
// 左子序列 比base小的数字的数组
quickSort(arr, left, pos - 1);
// 右子序列 比base大的数字的数组
quickSort(arr, pos + 1, right);
}
}
private static int partition(int[] arr, int left, int right) {
// 基准数据
int base = arr[left];
while (left < right) {
// 从后向前找，比base大，right--
while (left < right && arr[right] >= base) {
right--;
}
// 比base小，替换left所在位置的数字
arr[left] = arr[right];
// 从前向后找，比base小，left++
while (left < right && arr[left] <= base) {
left++;
}
// 比base大，替换right所在位置的数字
arr[right] = arr[left];
}
// 此时left=right，用base替换这个位置的数字
arr[left] = base;
return left; // 返回base的正确位置
}
}
🤯
