調整數組元素順序，你了解幾分？
前言
有一個整數數組，我們想按照特定規則對數組中的元素進行排序，比如：數組中的所有奇數位于數組的前半部分。
實現思路
我們通過一個實例來分析下：假設有這樣一個數組：[2, 4, 5, 6, 7, 8, 9, 11]，將奇數移動到最前面后，就是：[11, 9, 5, 7, 6, 8, 4, 2]。
通過觀察后，我們發現在掃描這個數組的時候，如果發現有偶數出現在奇數的前面， 就交換他們的順序，交換之后就符合要求了。
因此，我們可以維護兩個指針：
- 第一個指針初始化時指向數組的第一個數字，它只向后移動;
- 第二個指針初始化時指向數組的最后一個數字，它只向前移動;
在兩個指針相遇之前，第一個指針總是位于第二個指針的前面。如果第一個指針指向的數字是偶數，并且第二個指針指向的數字是奇數，則交換這兩個數字。
接下來，我們來通過圖來描述下上述例子交換指針的過程，如下所示：
- 第一個指針永遠指向偶數，如果不為偶數就向后移動;
- 第二個指針永遠指向奇數，如果不為奇數就向前移動;
- 當兩個指針各自指向的數都符合條件時，就交換兩個元素的位置;
- 交換完成后，重復上述步驟，直至兩個指針相遇或者第一個指針位于第二個指針之后則代表問題已得到解決。
實現代碼
有了思路之后，我們來看下實現代碼，如下所示：
export class AdjustArrayOrder {
// 指向數組元素的兩個指針：一個指向數組頭部、一個指向數組尾部
private begin = 0;
private end = 0;
// 調整數組中奇數與偶數元素的位置：奇數位于偶數前面
reorderOddEven(arr: Array<number>): void {
this.end = arr.length - 1;
while (this.begin < this.end) {
// 向后移動begin(轉成二進制跟1做與運算，運算結果為0就表示為偶數)，直至其指向偶數
while (this.begin < this.end && (arr[this.begin] & 0x1) !== 0) {
this.begin++;
}
// 向前移動end（轉成二進制跟1做與運算，運算結果為1就表示為奇數），直至其指向奇數
while (this.begin < this.end && (arr[this.end] & 0x1) === 0) {
this.end--;
}
// begin指向了偶數，end指向了奇數
if (this.begin < this.end) {
// 交換兩個元素的順序
[arr[this.begin], arr[this.end]] = [arr[this.end], arr[this.begin]];
}
}
// 重置指針位置
this.begin = 0;
this.end = 0;
}
}
代碼的可擴展
性如果數組中的元素不按照奇前偶后排列，我們需要將其按照大小進行劃分，所有負數都排在非負數的前面，應該怎么做?
聰明的開發者可能已經想到了方案：雙指針的思路還是不變，我們只需修改內層while循環的的判斷條件即可。
這樣回答沒有問題，確實解決了這個問題，那么如果再改改題目，我們需要把數組中的元素分為兩部分，能被3整除的數都在不能被3整除的數前面，應該怎么做?
經過思考后，我們發現這個問題無論再怎么改變都有一個共同的部分：雙指針的邏輯永遠不會變。變化的只是判斷條件，那么我們就可以把變化的部分提取成函數，當作參數讓調用者傳進來，這樣就完美的解決了這個問題，也正是我們所提及的代碼的可擴展性。
最后，我們來看下實現代碼，如下所示：
// 元素排序
reorder(arr: Array<number>, checkFun: (checkVal: number) => boolean): void {
this.end = arr.length - 1;
while (this.begin < this.end) {
// 向后移動begin
while (this.begin < this.end && !checkFun(arr[this.begin])) {
this.begin++;
}
// 向前移動end
while (this.begin < this.end && checkFun(arr[this.end])) {
this.end--;
}
// begin與end都指向了正確的位置
if (this.begin < this.end) {
// 交換兩個元素的順序
[arr[this.begin], arr[this.end]] = [arr[this.end], arr[this.begin]];
}
}
測試用例
我們先來測試下奇數在偶數之前的函數處理代碼能否正常執行，如下所示：
const adjustArrayOrder = new AdjustArrayOrder();
// 奇數在前
const arr = [2, 4, 5, 6, 7, 8, 9, 11];
adjustArrayOrder.reorderOddEven(arr);
console.log(arr);
執行結果如下所示：
最后，我們來測試下reorder函數能否正常執行：
- 負數在數組的最前面
// 負數在前
const checkMinusNumber = function (val: number) {
return val > 0;
};
const arr = [2, 4, 5, 6, 7, -8, -10 - 12, -2];
adjustArrayOrder.reorder(arr, checkMinusNumber);
console.log(arr);
- 能被3整除的數在數組的最前面
const checkDivisible = function (val: number) {
return val % 3 !== 0;
};
const arr = [2, 4, 5, 6, 3, 6, 9, 12];
adjustArrayOrder.reorder(arr, checkDivisible);
console.log(arr);
示例代碼
文中所舉代碼的完整版請移步：
- AdjustArrayOrder.ts[1]
- adjustArrayOrder-test.ts[2]
參考資料
[1]AdjustArrayOrder.ts: https://github.com/likaia/algorithm-practice/blob/e7f6a38021426397af60a73d4c6b8bf88548ba91/src/AdjustArrayOrder.ts#L2
[2]adjustArrayOrder-test.ts: https://github.com/likaia/algorithm-practice/blob/e7f6a38021426397af60a73d4c6b8bf88548ba91/src/test-case/adjustArrayOrder-test.ts#L3
[3]個人網站: https://www.kaisir.cn/
