关于typescript:调整数组元素顺序算法

前言

有一个整数数组，咱们想依照特定规定对数组中的元素进行排序，比方：数组中的所有奇数位于数组的前半部分。

本文将带大家实现这个算法，欢送各位感兴趣的开发者浏览本文。

实现思路

咱们通过一个实例来剖析下：假如有这样一个数组：[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
• adjustArrayOrder-test.ts

写在最初

至此，文章就分享结束了。

我是 神奇的程序员，一位前端开发工程师。

如果你对我感兴趣，请移步我的集体网站，进一步理解。

• 文中如有谬误，欢送在评论区斧正，如果这篇文章帮到了你，欢送点赞和关注😊
• 本文首发于神奇的程序员公众号，未经许可禁止转载💌