我这有一份秘籍，专门讲解数组的排序和扁平化的原理

flat

flat 方法其实就是用来扁平化数组的。在介绍它的用法之前，我们先来了解一下什么是根数组，什么是第 i 层数组（i >= 1）。

当我们用 let、const 或 var 定义了一个数组 arr，就称 arr 是根数组；如果 arr[i](i < arr.length)也是数组，那么 arr[i] 就是第一层数组；如果 arr[i][j] 也是数组，那么 arr[i][j] 就是第二层数组，以此类推......

flat 方法只有一个可选参数：

• depth：表示要扁平化到第几层的数组，默认值为 1。

用法

flat 方法默认扁平化到第一层的数组，例子如下：

const arr = [1, 2, [3, 4, [5]]];
const flatArr = arr.flat();
console.log(flatArr); // [1, 2, 3, 4, [5]]

我们也可以显示地指定扁平化到第几层数组：

const arr = [1, 2, [3, 4, [5]]];
const flatArr = arr.flat(2);
console.log(flatArr); // [1, 2, 3, 4, 5]

我们还可以传递 Infinity 参数给 flat 方法，表示无论有多少层数组，最终都会被扁平化：

const arr = [1, 2, [3, 4, [5, [6]]]];
const flatArr = arr.flat(Infinity);
console.log(flatArr); // [1, 2, 3, 4, 5, 6]

注意，flat 方法也不会遍历空槽元素：

const arr = [1, 2, [, 4]];
const flatArr = arr.flat();
console.log(flatArr); // [1, 2, 4]

实现原理

经过上面 flat 方法的用例，我们的第一反应肯定是：flat 方法的原理离不开递归。有的朋友很害怕递归，但在一些复杂的问题下，递归比递推（for 循环）好理解很多。

要想用好递归，关键在于，首先要想清楚我们定义的递归函数的功能是什么。

比如，我们定义一个递归函数来遍历数组的每一个元素：

// 遍历数组的元素
function traverse() {}

功能确定好了，紧接着，就要想明白，如何在函数体内用代码来表达这个功能。很明显，就是用 console.log() 来输出元素值：

function traverse() {
  console.log(array[index]); // 输出每一个元素值
}

看着函数体的代码就自然而然地知道，递归函数的参数是什么了：数组（array）和下标（index）：

// 遍历数组的元素
function traverse(array, index) {
  console.log(array[index]); // 输出每一个元素值
}

遍历完这个元素值，我们怎么遍历下一个元素值呢？很简单，递归调用 traverse 函数，index 参数为 index + 1 指向下一个元素：

function traverse(array, index) {
  console.log(array[index]); // 输出元素值
  traverse(array, index + 1); // 遍历下一个元素值
}

到这里，基本的递归函数功能就完成了，但别忘了最后一步，确定递归函数的最终条件，不然会一直递归下去。怎么确定终止条件？也是要根据递归函数功能来确定的，traverse 函数是用来遍历每一个数组中的元素，那么是不是遍历完最后一个元素就可以终止了？所以终止条件是：index === array.length：

function traverse(array, index) {
  // 最后一个元素已经遍历，终止递归。
  if (index === array.length) {
    return;
  }
  console.log(array[index]); // 输出元素值
  traverse(array, index + 1); // 遍历下一个元素值
}

当然了，我们也可以在调用递归函数之前就增加判断 — 当 index + 1 < array.length，才调用递归函数。如果下一个索引 index + 1 >= array.length，表示数组下标已经越界了，没有元素可以遍历了：

function traverse(array, index) {
  console.log(array[index]); // 输出元素值
  if (index + 1 < array.length) {
    traverse(array, index + 1); // 遍历下一个元素值
  }
}

这叫有条件的调用递归函数，同时也确定了终止条件。

所以说，递归最重要的就是确定好递归函数的功能，后面的所有事情（函数体代码、参数定义、递归条件、终止条件）都是围绕这个功能展开的。

有了上面递归思想的铺垫，我们已经能大概知道 flat 方法的原理需要一个递归函数，而这个递归函数的功能就是来扁平化到第 i 层数组的。具体思路如下：

1. 定义一个数组 res，用来保存最终的扁平化结果。
2. 递归函数会遍历数组中的每一个元素，如果当前元素不是数组，就直接添加到 res 数组中，否则是数组，并且当前数组的层数小于 i，那么就调用递归函数，继续走扁平化数组的逻辑。

从上面的实现思路来看，也确定了递归函数的参数，分别是数组（array）和当前数组的层数（depth）。

为了方便判断，我们将当前数组的层数是否小于 i 的判断修改为当前数组的层数是否大于 0，即：depth > 0，每次调用递归函数传递当前数组的层数为 depth - 1，具体代码实现如下：

Array.prototype._flat = function (depth = 1) {
  const res = []; // 保存结果
  // 递归函数，自执行一次
  (function recursionFlat(array, depth) {
    for (let i = 0; i < array.length; i++) {
      // 遍历非空槽元素
      if (i in array) {
        const value = array[i];
        if (Array.isArray(value) && depth > 0) {
          // 当前元素是数组且当前数组层数大于 0
          recursionFlat(value, depth - 1);
        } else {
          // 不是数组，直接存放到 res 数组中
          res.push(value);
        }
      }
    }
  })(this, depth);

  return res;
};

sort

sort 方法也是大家使用比较频繁的一个数组方法，它会就地对数组的元素进行排序，会修改原数组。默认排序的逻辑是将元素转换为字符串，然后按照它们的 UTF-16 码元值升序排序，也就是字符串的比较，比如：'a' < 'b'。

sort 方法只有一个可选参数：

• compareFn：定义排序顺序的函数，该函数有 a 和 b 两个参数，a 表示第一个用于比较的元素，b 表示第二个用于比较的元素。该函数的返回值是一个数字，有三种情况：

  • > 0：a 会排在 b 的后面
  • < 0：a 会排在 b 的前面
  • ===0：a 和 b 保持原来的顺序

用法

sort 方法默认是将元素值转换为字符串进行排序的，比如：

const arr = [1, 2, 10, 15, 20];
arr.sort();
console.log(arr); // [1, 10, 15, 2, 20]

const arr1 = ["one", "two", "three", "four"];
arr1.sort();
console.log(arr1); // ['four', 'one', 'three', 'two']

我们也可以传入比较函数来对数组的元素进行升序排序或降序排序：

const arr = [1, 2, 10, 15, 20];
// 升序排序
arr.sort(function(a, b) {
  return a - b;
});
console.log(arr); // [1, 2, 10, 15, 20]

const arr = [1, 2, 10, 15, 20];
// 降序排序
arr.sort(function(a, b) {
  return b - a;
});
console.log(arr); // [20, 15, 10, 2, 1]

如果数组里有 null、undefined 或空槽元素，那么它们都会排在最后面，并且顺序永远是 null，undefined，空槽元素，比如：

 const arr = [1, , 3, undefined, 2, null];
arr.sort(function(a, b) {
  return a - b;
});
console.log(arr); // [1, 2, 3, null, undefined, 空]

实现原理

sort 方法会根据数组中元素的个数来选择不同的排序策略，有两种情况：

1. 当 n <= 10 时，采用插入排序。
2. 当 n > 10 时，采用快速排序。

插入排序

假定现在是对数组做升序排序，插入排序的思路是：

1. 一开始就认定第一个元素是有序的数组。
2. 而后面的每一个元素都会在这个有序的数组从尾到头，找到比它小的第一个元素，然后插入到这个元素的后面。

代码实现：

// 升序排序
// 插入排序 — 假设第一个数就是有序的数组，后面每一个数组都会插入到这个有序数组的正确位置
function insertionSort(array) {
  let tmp, j;
  for (let i = 1; i < array.length; i++) {
    tmp = array[i];
    j = i - 1;
    // 从后往前找到第一个比 tmp 小的数，并将比 tmp 大的数往后移动
    while (j >= 0 && array[j] > tmp) {
      array[j + 1] = array[j];
      j--;
    }
    // 插入到第一个比 tmp 小的数的后面
    array[j + 1] = tmp;
  }
}

const arr = [3, 2, 4, 1];
insertionSort(arr);
console.log(arr); // [1, 2, 3, 4]

平均的时间复杂度：O(n2)O(n^2)O(n2)

快速排序

依然假定是对数组做升序排序，快速排序的思路是：

1. 先找一个分界点，一般是数组的第一个元素。
2. 遍历第二个元素到最后一个元素，设 left 是从左往右的索引，执行 left++，直到找到第一个大于分界点的元素，设 right 是从右往左的索引，执行 right--，直到找到第一个小于等于分界点的元素。
3. 将这两个元素进行互换
4. 重复第二个和第三个步骤，left > right，说明这时候元素已经交换完毕，并且这时候 right 或者 left - 1 肯定是小于分界点的元素。
5. 由于分界点是第一个元素，所以最后把第一个元素和 right 元素进行互换，就变成了分界点元素的左边全部都是小于等于它的，右边全部都是大于它的。
6. 实际上我们就完成了分界点元素的排序，因为它已经落到了正确的位置上。然后再将分界点左边的所有元素和右边的所有元素再次执行第一个到第五个步骤，直到分界点元素的左边和右边只有一个元素。

快速排序的代码实现肯定离不开递归，所以我在前面花了点篇幅来介绍递归的用法

代码实现：

function quickSort(array, start, end) {
  // 递归终止条件 — 数组内只有一个元素，
  // 单个元素的数组就是有序的，不需要再执行下面的流程
  if (start >= end) return;
  
  const pivot = array[start]; // 分界点元素
  let left = start + 1, // 从左往右的索引
    right = end; // 从右往左的索引
  
  while (left <= right) {
    // 从左往右找到第一个大于分界点的元素
    while (left <= right && array[left] <= pivot) {
      left++;
    }
    // 从右往左找到第一个小于或等于分界点的元素
    while (left <= right && array[right] > pivot) {
      right--;
    }
    // 注意这里必须满足 left < right，才可以交换元素。
    // 因为有可能找元素的时候就出现了 left > right 的情况，
    // 如果这时候无条件的交换，就会得到错误的顺序。
    if (left < right) {
      // 交换这两个元素 
      [array[left], array[right]] = [array[right], array[left]];
    }
  }
  // 将分界点元素放到合适的位置，
  // 使得：分界点左边的所有元素小于等于分界点，右边的所有元素大于分界点
  [array[start], array[right]] = [array[right], array[start]];
  
  // 对左边的所有元素和右边的所有元素重复执行上述逻辑
  quickSort(array, start, right - 1);
  quickSort(array, right + 1, end);
}

const arr = [3, 2, 4, 1];
quickSort(arr, 0, arr.length - 1);
console.log(arr); // [1, 2, 3, 4]

平均的时间复杂度：O(nlogn)O(nlogn)O(nlogn)

null、undefined、空元素的处理

前面说了 null、undefined 或空槽元素会排在最终结果数组的最后，所以我们需要声明四个数组来分别存放 null、undefined、空槽元素以及其他元素，具体代码如下：

const nullArr = []; // 存放 null
const undefinedArr = []; // 存放 undefined
const emptyArr = []; // 存放空槽元素
const newArr = []; // 存放其他元素
for (let i = 0; i < this.length; i++) {
  if (i in this) {
    if (this[i] === null) {
      nullArr.push(this[i]);
    } else if (this[i] === undefined) {
      undefinedArr.push(this[i]);
    } else {
      newArr.push(this[i]);
    }
  } else {
    // 空元素
    emptyArr.length++;
  }
}

然后用 newArr 数组来执行插入排序或快速排序，再将上面四个数组的元素值按顺序赋值给原数组：

//...执行插入排序或快速排序

this.length = 0; // 清空原数组
newArr.forEach((ele) => this.push(ele)); // 将排序好的元素赋值给原数组
nullArr.forEach((ele) => this.push(ele)); // 将所有 null 赋值给原数组
undefinedArr.forEach((ele) => this.push(ele)); // 将所有 undefined 赋值给原数组
this.length += emptyArr.length; // 赋值空元素

完整的代码实现

Array.prototype._sort = function (compareFn) {
  // 默认排序逻辑
  compareFn =
    compareFn ||
    function (a, b) {
      a = a.toString ? a.toString() : a;
      b = b.toString ? b.toString() : b;
      if (a > b) return 1;
      if (a < b) return -1;
      return 0;
    };

  // 处理 null, undefined, 空槽元素
  const nullArr = [];
  const undefinedArr = [];
  const emptyArr = [];
  const newArr = [];
  for (let i = 0; i < this.length; i++) {
    if (i in this) {
      if (this[i] === null) {
        nullArr.push(this[i]);
      } else if (this[i] === undefined) {
        undefinedArr.push(this[i]);
      } else {
        newArr.push(this[i]);
      }
    } else {
      // 空元素
      emptyArr.length++;
    }
  }

  // 插入排序
  function insertionSort(array, start, end) {
    let tmp, j;
    for (let i = 1; i <= end; i++) {
      tmp = array[i];
      j = i - 1;
      // compareFn(tmp, array[j]) < 0 等价于 tmp < array[j]
      while (j >= 0 && compareFn(tmp, array[j]) < 0) {
        array[j + 1] = array[j];
        j--;
      }
      array[j + 1] = tmp;
    }
  }
  // 快速排序
  function quickSort(array, start, end) {
    // 递归终止条件 — 数组内只有一个元素，
    // 单个元素的数组就是有序的，不需要再执行下面的流程
    if (start >= end) return;

    const pivot = array[start]; // 分界点元素
    let left = start + 1, // 从左往右的索引
      right = end; // 从右往左的索引

    while (left <= right) {
      // compareFn(array[left], pivot) <= 0 等价于 array[left] <= pivot
      while (left <= right && compareFn(array[left], pivot) <= 0) {
        left++;
      }
      // compareFn(array[right], pivot) > 0 等价于 array[right] > pivot
      while (left <= right && compareFn(array[right], pivot) > 0) {
        right--;
      }
      // 注意这里必须满足 left < right，才可以交换元素。
      // 因为有可能找元素的时候就出现了 left > right 的情况，
      // 如果这时候无条件的交换，就会得到错误的顺序。
      if (left < right) {
        [array[left], array[right]] = [array[right], array[left]];
      }
    }
    // 将分界点元素放到合适的位置，
    [array[start], array[right]] = [array[right], array[start]];

    // 对左边的所有元素和右边的所有元素重复执行上述逻辑
    quickSort(array, start, right - 1);
    quickSort(array, right + 1, end);
  }

  if (this.length <= 10) {
    insertionSort(newArr, 0, newArr.length - 1);
  } else {
    quickSort(newArr, 0, newArr.length - 1);
  }

  this.length = 0; // 清空原数组
  newArr.forEach((ele) => this.push(ele)); // 将排序好的元素赋值给原数组
  nullArr.forEach((ele) => this.push(ele)); // 将所有 null 赋值给原数组
  undefinedArr.forEach((ele) => this.push(ele)); // 将所有 undefined 赋值给原数组
  this.length += emptyArr.length; // 追加空槽元素
};

总结

1. 递归是实现 flat 和 sort 方法的关键所在，所以理解递归的执行逻辑很重要。
2. sort 方法会根据数组元素的个数来采取不同的排序算法，若元素个数小于等于 10，就用插入排序，否则就使用快速排序。同时内部还需要处理 null、undefined和空槽元素。
3. 插入排序的思路是认定第一个元素就是有序的数组，后面的每一个元素都会在这个有序的数组从尾到头，找到比它小的第一个元素，然后插入到这个元素的后面（升序排序）。
4. 快速排序的思路是先找一个分界点，一般来说就是待排序数组中的第一个元素，从待排序数组中的第二个元素开始从左往右找到第一个大于分界点的元素，再从右往左找到第一个小于等于分界点的元素，交换这两个元素，直到最后分界点的左边都是小于等于它的元素，右边都是大于它的元素。再递归分界点左边的所有元素和右边的所有元素进行排序（升序排序）。

总得来说，flat 方法就只是用递归的思想来实现扁平化的；而 sort 方法不仅仅使用到了递归的思想，还涉及到了很多细节上的处理，一次看不明白没关系，能大概理解其实现思路就行，后续再反复琢磨，理解其中的奥妙。