一、简介
步骤如下：
- 从数列中挑出一个元素，称为 “基准”（pivot）;
- 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
- 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序；
二、编码如下
代码语言：javascript复制/**
* 快速排序
*
* @author xjf
* @date 2020/8/28 16:08
*/
public class QuickSort {
public static void main(String[] args) {
int[] arr = new int[]{1, 20, 8, 666, 56, 256, 7, 256, 351, 666, 96};
System.out.println("排序前：");
for (int i : arr) {
System.out.print(i " t");
}
System.out.println();
quickSort(arr, 0, arr.length -1);
System.out.println("排序后：");
for (int i : arr) {
System.out.print(i " t");
}
}
/**
* 快速排序实现方法
*
* @param arr 原始无序数组
* @param low 数组起始索引
* @param high 数组最大索引
*/
private static void quickSort(int[] arr, int low, int high){
if (low < high) {
int i = low;
int j = high;
// 取第一个数为基准数
int x = arr[low];
// 一轮排序需要将元素都遍历一遍
while (i < j) {
// 首先从右往左遍历，直到找到一个比基准数小的位置索引
while (i < j && arr[j] >= x) {
j--;
}
// 将在右边小于基准的数赋值到左边的位置 i 上，初次 i 位置的数就是基准数，被保存在 x 变量上，所以覆盖没问题
if (i < j) {
arr[i ] = arr[j];
}
// 再从左往右遍历，找比基准数大的数
while (i < j && arr[i] < x) {
i ;
}
// 将左边大的数，赋值给右边的位置 j 上，此时 j 这个位置的数已经被赋值到左边去了，所以直接覆盖没问题
if (i < j) {
arr[j--] = arr[i];
}
}
// 上面的外层循环条件为 i < j，所以跳出循环时，i = j。
// 此处这个点的值是被赋值到其他位置上的，所以需要填充这个点的真实值，即为基准值
arr[i] = x;
// 上面执行一次排序后，数据根据基准值分成了两块，再分别对两块进行同样的排序
quickSort(arr, low, i - 1);
quickSort(arr, i 1, high);
}
}
}
