我们取中间值作为基准值，又两个索引分别从左端和右端向中间靠拢，比较大小，将小于基准值的归到左边，大于基准值的归到右边，这时l与r可能都指向基准值的位置，但是下一步两个索引自增，l大于r(但是要保证不超出边界即left与right)，这是l作为右半部分的新的递归的left，right就是right；r作为左半部分的新的递归的right，left就是left，直到排序剩下一个就是有序的了
代码实现
import java.util.Arrays;
/**
* @Description: 快速排序第一种
* @Author: LinZeLiang
* @Date: 2020-10-04
*/
public class QuickSortFirst {
public static void main(String[] args) {
int[] a = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
quickSort(a, 0, a.length - 1);
System.out.println(Arrays.toString(a));
}
/**
* @param a 待排序数组
* @param left 指向第一个元素
* @param right 指向最后一个元素
*/
public static void quickSort(int[] a, int left, int right) {
//记录下基准值（中间值）
int pivot = a[(left + right) / 2];
int l = left;
int r = right;
while (l <= r) {
//直到找到比基准值大的
while (a[l] < pivot) {
l++;
}
//直到找到比基准值小的
while (a[r] > pivot) {
r--;
}
//交换两边数字，l向右移动一位，r向左移动一位
if (l <= r) {
int temp = a[l];
a[l] = a[r];
a[r] = temp;
l++;
r--;
}
}
//将左半部分递归排序
if (r > left) {
quickSort(a, left, r);
}
//将右半部分进行递归排序
if (l < right) {
quickSort(a, l, right);
}
}
}
将数组的第一个数作为基准值，思想其实和第一个一样，只是实现的方法不一样而已
代码实现
import java.util.Arrays;
/**
* @Description: 快速排序第二种
* @Author: LinZeLiang
* @Date: 2020-10-04
*/
public class QuickSortSecond {
public static void main(String[] args) {
int[] a = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
quickSort(a, 0, a.length - 1);
System.out.println(Arrays.toString(a));
}
/**
* 快速排序
*
* @param a 待排序数组
* @param left 指向子数组第一个索引
* @param right 指向子数组最后一个索引
*/
public static void quickSort(int[] a, int left, int right) {
if (left < right) {
//将链表一分为二得到中间值
int center = partion(a, left, right);
//然后分别再对两边递归排序
quickSort(a, left, center - 1);
quickSort(a, center + 1, right);
}
}
/**
* 进行分区
*
* @param a 待分区数组
* @param left 指向数组第一个索引
* @param right 指向数组最后一个索引
*/
public static int partion(int[] a, int left, int right) {
//将第一个值作为基准值
int pivot = a[left];
while (left < right) {
//当队尾元素大于等于pivot时，往前移动，直到找到小于pivot
//与基准值pivot比较时必须要添加等号，否则出现一样的数字就会进入无限递归循环
while (left < right && a[right] >= pivot) {
right--;
}
//队尾元素小于pivot，将其赋值给left
a[left] = a[right];
//当队头元素小于等于pivot时，往后移动指针，直到大于基准值
while (left < right && a[left] <= pivot) {
left++;
}
//队头元素大于pivot，将其赋值给right
a[right] = a[left];
}
//由于基准值pivot还处于未分配状态，
//跳出循环时left和right相等,此时的left或right就是pivot的正确索引位置
//由原理部分可以很清楚的知道left位置的值并不是pivot,所以需要将tmp赋值给a[left]
//第一个循环时将right赋值给left，right处于未分配状态，第二个循环时将left的赋值给right，left处于未分配状态
a[left] = pivot;
return left;
}
}
原文：https://www.cnblogs.com/linzedian/p/13776872.html