TypeScript調(diào)整數(shù)組元素順序算法

更新時間：2022年04月19日 11:11:39 作者：神奇的程序員

數(shù)組類型在TS中可以使用多種方式,比較靈活,下面這篇文章主要給大家介紹了關(guān)于TypeScript調(diào)整數(shù)組元素順序算法的相關(guān)資料,文中通過實例代碼介紹的非常詳細,需要的朋友可以參考下

前言

有一個整數(shù)數(shù)組，我們想按照特定規(guī)則對數(shù)組中的元素進行排序，比如：數(shù)組中的所有奇數(shù)位于數(shù)組的前半部分。

本文將帶大家實現(xiàn)這個算法，歡迎各位感興趣的開發(fā)者閱讀本文。

實現(xiàn)思路

我們通過一個實例來分析下：假設(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ù)的前面，就交換他們的順序，交換之后就符合要求了。

因此，我們可以維護兩個指針：

第一個指針初始化時指向數(shù)組的第一個數(shù)字，它只向后移動；
第二個指針初始化時指向數(shù)組的最后一個數(shù)字，它只向前移動；

在兩個指針相遇之前，第一個指針總是位于第二個指針的前面。如果第一個指針指向的數(shù)字是偶數(shù)，并且第二個指針指向的數(shù)字是奇數(shù)，則交換這兩個數(shù)字。

接下來，我們來通過圖來描述下上述例子交換指針的過程，如下所示：

第一個指針永遠指向偶數(shù)，如果不為偶數(shù)就向后移動；
第二個指針永遠指向奇數(shù)，如果不為奇數(shù)就向前移動；
當兩個指針各自指向的數(shù)都符合條件時，就交換兩個元素的位置；
交換完成后，重復(fù)上述步驟，直至兩個指針相遇或者第一個指針位于第二個指針之后則代表問題已得到解決。

實現(xiàn)代碼

有了思路之后，我們來看下實現(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)成二進制跟1做與運算，運算結(jié)果為0就表示為偶數(shù))，直至其指向偶數(shù)
      while (this.begin < this.end && (arr[this.begin] & 0x1) !== 0) {
        this.begin++;
      }

      // 向前移動end（轉(zhuǎn)成二進制跟1做與運算，運算結(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;
  }
}

代碼的可擴展性

如果數(shù)組中的元素不按照奇前偶后排列，我們需要將其按照大小進行劃分，所有負數(shù)都排在非負數(shù)的前面，應(yīng)該怎么做？

聰明的開發(fā)者可能已經(jīng)想到了方案：雙指針的思路還是不變，我們只需修改內(nèi)層while循環(huán)的的判斷條件即可。

這樣回答沒有問題，確實解決了這個問題，那么如果再改改題目，我們需要把數(shù)組中的元素分為兩部分，能被3整除的數(shù)都在不能被3整除的數(shù)前面，應(yīng)該怎么做？

經(jīng)過思考后，我們發(fā)現(xiàn)這個問題無論再怎么改變都有一個共同的部分：雙指針的邏輯永遠不會變。變化的只是判斷條件，那么我們就可以把變化的部分提取成函數(shù)，當作參數(shù)讓調(diào)用者傳進來，這樣就完美的解決了這個問題，也正是我們所提及的代碼的可擴展性。

最后，我們來看下實現(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í)行：

負數(shù)在數(shù)組的最前面

// 負數(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);