对于快排有三种版本。
# 1. 版本1
在前面的简单排序算法中所实现的排序算法为第一种，即在数组的左边或者右边选定端点值作为轴值，规定左边下标`i`及其之前的元素为小于等于轴值的部分，而下标`j`及其之后的元素为大于轴至的元素。然后开始在左右两端进行扫描，其过程可以描述为下面的图示：
<img src="http://weizu_cool.gitee.io/gif-source/images/屏幕截图 2022-01-05 103301.png"/>
对应代码：
~~~
/**
* 快排版本1，即选择左边或者右边的端点值来作为轴值，然后进行改数的最终位置的放置，并将数据划分为两个部分
* @param arr 待排序数组
*/
public void quickSortVersion_1(int[] arr){
if(arr == null || arr.length == 0) return;
quickSortV_1(arr, 0, arr.length - 1);
}
private void quickSortV_1(int[] arr, int left, int right) {
if(left < right){
int mid = partitionV_1(arr, left, right);
quickSortV_1(arr, left, mid - 1);
quickSortV_1(arr, mid + 1, right);
}
}
private int partitionV_1(int[] arr, int left, int right) {
int value = arr[left];
while(left < right){
while(left < right && arr[right] > value) right--;
swap(arr, left, right);
while(left < right && arr[left] <= value) left++;
swap(arr, left, right);
}
return left;
}
~~~
# 2. 版本2
注意到一点，就是如果数组中的当前轴值在数组中含有多个，比如上面的案例中第一次划分使用`arr[0]=4`，不妨打印一下每趟排序的结果，如下图所示：
<img src="http://weizu_cool.gitee.io/gif-source/images/屏幕截图 2022-01-05 104908.png"/>
注意到一点就是在第一趟排序的结果中，倒数第二个数，也就是第一个`4`放置在了最终位置，但是对于数组中其余的两个重复的`4`，却还需要再次递归的进行快排。这个过程无疑是重复了。
所以在版本`2`中，考虑使用前面的[快排的一次数据划分](https://www.kancloud.cn/the_road_of_android/algroithm/2591416)中的三类数据划分算法，也就是：
~~~
/**
* 快排第二个版本，改动部分为partition，也就是将数据划分为了三个部分，小于轴值、等于轴值和大于轴值
* @param arr 待排序数组
*/
public void quickSortVersion_2(int[] arr){
if(arr == null || arr.length == 0) return;
quickSortV_2(arr, 0, arr.length - 1);
}
private void quickSortV_2(int[] arr, int left, int right) {
if(left < right){
int[] partition = partitionV_2(arr, left, right);
for (int i : arr) {
System.out.print(i+"\t");
}
System.out.println();
quickSortV_2(arr, left, partition[0] - 1);
quickSortV_2(arr, partition[1] + 1, right);
}
}
private int[] partitionV_2(int[] arr, int left, int right) {
int i = left - 1, j = right, k = left, value = arr[left];
// 假定0-i为小于value，j及其之后为大于value，均为其边界
while(k <= j){
if(arr[k] > value){ // 大于轴值，就放置在右边，并且右边界左移一位
swap(arr, k, j);
j--;
} else if(arr[k] < value) { // 小于轴值，放置在左边，左边界右移一位
i++;
swap(arr, k, i);
} else{ // 等于轴值，不移动，即放置在中间，直接后移即可
k++;
}
}
return new int[]{i+1, j}; // 返回数组中等于轴值的这些数排序后的端点下标
}
~~~
对于数组`arr=[4, 4, 1, 0, 4, 6, 3, 4, 7, 4, 8, 0, 1, 4]`，在这个版本的排序中，每趟排序的结果为：
<img src="http://weizu_cool.gitee.io/gif-source/images/屏幕截图 2022-01-05 112531.png"/>
# 3. 版本3
对于版本`2`中解决了数组中重复元素选为轴值的问题，但是值得注意到一点：比如当选定的左边的轴值的右边的所有元素都比其大，那么问题就会退化，而不是折半递归了。所以对于快排划分中轴值的划分可以采用随机值的方式。
~~~
/**
* 快排第三个版本，改动部分为轴值的选择为随机选择
*
* @param arr 待排序数组
*/
public void quickSortVersion_3(int[] arr) {
if (arr == null || arr.length == 0) return;
quickSortV_3(arr, 0, arr.length - 1);
}
private void quickSortV_3(int[] arr, int left, int right) {
if (left < right) {
int[] partition = partitionV_3(arr, left, right);
quickSortV_2(arr, left, partition[0] - 1);
quickSortV_2(arr, partition[1] + 1, right);
}
}
private int[] partitionV_3(int[] arr, int left, int right) {
int i = left - 1, j = right, k = left;
// 随机选择一个值作为轴值
int index = left + (int) (Math.random() * (right - left));
int value = arr[index];
// 假定0-i为小于value，j及其之后为大于value，均为其边界
while (k <= j && i < j) {
if (arr[k] > value) { // 大于轴值，就放置在右边，并且右边界左移一位
swap(arr, k, j);
j--;
} else if (arr[k] < value) { // 小于轴值，放置在左边，左边界右移一位
i++;
swap(arr, k, i);
} else { // 等于轴值，不移动，即放置在中间，直接后移即可
k++;
}
}
return new int[]{i + 1, j}; // 返回数组中等于轴值的这些数排序后的端点下标
}
~~~
