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