對于快排有三種版本。
# 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`中，考慮使用前面的[快排的一次數據劃分](http://www.hmoore.net/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}; // 返回數組中等于軸值的這些數排序后的端點下標
}
~~~
