快排的思想：
在给定的数组中随机找一个划分值R，设法让数组中的划分值R左边都是比R小的元素，右边都是比R大的元素。
快排思路步骤：
- 随机在数组中选取一个值，作为划分值；
- 进行排序，将数组中比划分值小的元素放到划分值左侧，比划分值大的元素放到划分值右侧；
- 对划分值左侧、右侧的子数组继续进行上述步骤；
- 最后数组有序。
PS：
每次排序后都会确定一个元素的最终位置，就是划分值被排好了。
快排代码步骤：
- 在数组中随机找出一个元素作为划分值；
- 将该元素与数组最后一个元素进行交换，交换的目的是方便直接用arr[length-1]来取到划分值；
- 进行排序，将数组中比划分值小元素的放到数组最左侧，将数组中比划分值大的元素放到数组最右侧；
- 将划分值放到合适的位置，即用划分值右侧数组的最左侧元素与划分值进行交换；
- 返回交换后划分值所在的位置，方便后面分区递归；
- 对划分值位置左侧和右侧的数组分别进行递归排序；
- 结束。
对应代码如下：
public class QuickSort {
@Test
public void testQuickSort() {
int[] arr = {3, 5, 7, 3, 2, 7};
quickSort(arr, 0, arr.length - 1);
SortUtils.display(arr);
}
private void quickSort(int[] arr, int L, int R) {
// 递归出口
if (L >= R) return;
// 选取数组中的随机值，作为划分值
int random = L + new Random().ints(0, R - L + 1).findAny().getAsInt();
// 将划分值与数组最后一个元素交换，方便拿到划分值
swap(arr, random, R);
// 排序，返回划分值最终位置
int boundary = partition(arr, L, R);
// 对划分值左侧数组排序
quickSort(arr, L, boundary-1);
// 右侧排序
quickSort(arr, boundary+1, R);
}
private int partition(int[] arr, int L, int R) {
// 定义左侧边界，每当有元素比划分值小，纳入左侧数组，边界+1
int less = L - 1;
// 定义右侧边界，因为数组最右侧是划分值，所以不+1；每当有元素比划分值大，则放到最右边（划分值的左侧），边界-1；
int more = R;
while (L < more) {
if (arr[L] < arr[R]) { // 元素比划分值小，放到左边
swap(arr, L++, ++less);
} else if (arr[L] >= arr[R]) { // 元素比划分值大，放到右边
swap(arr, L, --more);
}
}
swap(arr, more, R); // 将划分值换回正确位置，此时左侧都比它小，右侧都比它大
return more;
}
private void swap(int[] arr, int a, int b) {
int tmp = arr[a];
arr[a] = arr[b];
arr[b] = tmp;
}
}
快排优化
在上面的快排中，我们发现如果数组中有元素与划分值相等，它依然会被交换到右侧区域（比划分值大的区域），后面的递归中，肯定还会换回来，这样做了重复的交换动作。优化点就是，让与划分值相等的元素保持原位置不动。
代码如下
public class QuickSort {
@Test
public void testQuickSort() {
int[] arr = {4, 1, 5, 3};
quickSort(arr, 0, arr.length - 1);
SortUtils.display(arr);
}
private void quickSort(int[] arr, int L, int R) {
if (L < R) {
int random = L + (int) (Math.random() * (R - L + 1));
SortUtils.swap(arr, random, R);
int[] part = partition(arr, L, R);
quickSort(arr, L, part[0] - 1); // 划分值已经放在了正确的位置，所以只需要排左侧和右侧的数组就好了
quickSort(arr, part[1] + 1, R);
}
}
private int[] partition(int[] arr, int L, int R) {
int less = L - 1; // 小于arr[R]区域的右边界
int more = R; // 大于arr[R]区域的左边界
while (L < more) { // 指针撞到大于区域的左边界则停止
if (arr[L] < arr[R]) { // 如果指针指向的数小于划分值，则该数与less区域的下一个数交换，less范围右移1位
SortUtils.swap(arr, L++, ++less);
} else if (arr[L] == arr[R]) { // 如果等于划分值，指针L右移，不做任何交换
L++;
} else if (arr[L] > arr[R]) { // 如果大于划分值，将数与 more 区域的左侧一个数交换，指针L此时指向的是一个新数，不右移
SortUtils.swap(arr, --more, L);
}
}
SortUtils.swap(arr, more, R); // 指针L与more碰撞后，需要将划分值放回原有位置，即more区域的最左侧，这样，此时划分值右侧的数都比划分值大
return new int[]{less + 1, more}; // less+1 的位置就是跟划分值相等的值，而more正好指向划分值，所以是 less+1,和more；
// 因为中间可能会有多个与划分值相等的元素，所以递归数组的边界肯定就不能用一个划分值的位置来表示了，需要用两个边界值来表示。
}
}
