# 1. 兩類數據劃分
## 1.1 問題描述
給定一個數組和一個數字`num`，把數組中小于`num`的數字放在數組的左邊，大于`num`的數字放在數組的右邊。要求額外空間復雜度為`O(1)`，時間復雜度為`O(n)`。
## 1.2 問題分析
對于這個問題，最直觀的做法就是采用類似快排的思路，定義兩個指針`i`和`j`。比如下面的圖示：
<img src='http://weizu_cool.gitee.io/gif-source/images/屏幕截圖 2022-01-04 101629.png' />
對應代碼：
~~~
/**
* 一次劃分結果，處理兩類劃分問題
* 即：默認數組中不存在等于num的元素
* @param arr 待劃分數組
* @param num 劃分邊界
*/
public void partition(int[] arr, int num){
int left = 0, right = arr.length - 1;
while(left <= right){
while(arr[left] < num) left++;
while(arr[right] > num) right--;
if(left <= right) swap(arr, left, right);
}
}
/**
* 異或運算進行交換兩個數字
* @param arr 數組
* @param left 左邊下標
* @param right 右邊下標
*/
private void swap(int[] arr, int left, int right) {
int temp = arr[left] ^ arr[right];
arr[left] = temp ^ arr[left];
arr[right] = arr[left] ^ temp;
}
~~~
以`arr=[1, 6, 3, 2, 5, 1, 7, 2, 10]`，`num=4`為案例，運行結果：
<img src="http://weizu_cool.gitee.io/gif-source/images/屏幕截圖 2022-01-04 104836.png"/>
那么根據上面的思路，我們可以規定左邊的部分為嚴格小于`num`的部分，對于其后的元素我們使用掃描加交換的方式可以簡化一下這個算法過程，如下圖所示：
<img src='http://weizu_cool.gitee.io/gif-source/images/屏幕截圖 2022-01-04 103042.png' />
對應代碼：
~~~
/**
* 一次劃分結果，處理兩類劃分問題
* 即：默認數組中不存在等于num的元素
* @param arr 待劃分數組
* @param num 劃分邊界
*/
public void partition(int[] arr, int num){
int i = -1;
for (int j = 0; j < arr.length; j++) {
if(arr[j] > num) continue;
swap(arr, i + 1, j);
i++;
}
}
/**
* 異或運算進行交換兩個數字
* @param arr 數組
* @param left 左邊下標
* @param right 右邊下標
*/
private void swap(int[] arr, int left, int right) {
int temp = arr[left] ^ arr[right];
arr[left] = temp ^ arr[left];
arr[right] = arr[left] ^ temp;
}
~~~
以`arr=[1, 6, 3, 2, 5, 1, 7, 2, 10]`，`num=4`為案例，運行結果：
<img src='http://weizu_cool.gitee.io/gif-source/images/屏幕截圖 2022-01-04 104642.png'/>
# 2. 三類數據劃分
注意到在上面的兩類數據的劃分中沒有考慮等于問題，而這個問題是比可避免的。所以這里我們需要繼續優化這個問題。
類似的，這里還是先考慮快排的一次劃分，這里摘抄一下快排的一次排序：
~~~
/**
* 按照左邊第一個數作為軸值進行比較劃分
* @param arr 待排序數組
* @param left 左邊界
* @param right 右邊界
* @return 軸值的最終有序位置
*/
private int partition(int[] arr, int left, int right) {
int value = arr[left];
while (left < right) {
while (left < right && arr[right] >= value) {
right--;
}
swap(arr, right, left);
while (left < right && arr[left] <= value) {
left++;
}
swap(arr, right, left);
}
return left;
}
~~~
以案例`arr=[4, 6, 3, 2, 5, 4, 1, 7, 4, 10, 4]`為例，然后打印一下每次劃分的結果：
<img src='http://weizu_cool.gitee.io/gif-source/images/屏幕截圖 2022-01-04 112202.png'/>
這里可以發現，在快排中，存在相同元素的`num`即使作為軸值，也不會達到相同的`num`值放置在中間一堆。而是在不斷的遞歸子問題劃分中不斷有序。所以如果要做到三部分數據的有序，我們需要確保有嚴格的數據界限邏輯劃分，類似于上面的第二種解法，如下圖所示：
<img src="http://weizu_cool.gitee.io/gif-source/images/屏幕截圖 2022-01-04 154000.png"/>
對應代碼如下：
~~~
/**
* 劃分數組數據為三部分
* @param arr 待劃分數組
* @param num 劃分值
*/
private void partitionWithThreePart(int[] arr, int num) {
int i = 0, j = arr.length - 1, k = 0;
while(k <= j){
if(arr[k] < num) { // 小于num的情況
swap(arr, i, k);
if(i == k) k++;
i++;
}else if(arr[k] > num){ // 大于num的情況
swap(arr, k, j);
j--;
} else{ // 等于num的情況
k++;
}
}
}
/**
* 異或運算進行交換兩個數字
* @param arr 數組
* @param left 左邊下標
* @param right 右邊下標
*/
private void swap(int[] arr, int left, int right) {
int temp = arr[left] ^ arr[right];
arr[left] = temp ^ arr[left];
arr[right] = arr[left] ^ temp;
}
~~~
