保持函数式不可变性，避免冒泡排序中的额外slice()调用

你的问题本质是类型标注与实际数组实例不匹配导致的多余slice()调用——内部排序过程中创建的数组本身就是普通可变数组（通过[...arr]生成），只是被你标注成了ReadonlyArray<T>，最后用slice()只是为了做类型转换，完全没必要。

下面给两种优化方案，都能去掉末尾的slice()：

方案一：调整内部函数的类型标注（更清晰） #

直接让内部函数返回普通数组类型T[]，而不是ReadonlyArray<T>，这样整个流程的类型更贴合实际创建的数组：

export default function bubbleSort<T>(array: ReadonlyArray<T>, compare: (a: T, b: T) => number): T[] {
  // swap直接返回T[]，因为newArr是通过spread创建的普通数组
  const swap = (arr: ReadonlyArray<T>, i: number, j: number): T[] => {
    const newArr = [...arr];
    [newArr[i], newArr[j]] = [newArr[j], newArr[i]];
    return newArr;
  };

  // bubblePass返回[T[], boolean]，适配swap的返回类型
  const bubblePass = (arr: ReadonlyArray<T>, n: number): [T[], boolean] => {
    return arr.slice(1, n).reduce(
      ([accArray, swapped], _, i) => {
        if (compare(accArray[i], accArray[i + 1]) > 0) {
          return [swap(accArray, i, i + 1), true];
        }
        // 初始accArray是传入的arr，断言为T[]是安全的，因为我们调用时传入的是普通数组
        return [accArray as T[], swapped];
      },
      // 初始值把arr断言为T[]，因为sort函数传入的初始arr是[...array]（普通数组）
      [arr as T[], false] as [T[], boolean],
    );
  };

  // sort函数接收和返回都是T[]，类型统一
  const sort = (arr: T[], n: number): T[] => {
    if (n <= 1) return arr;
    const [newArr, swapped] = bubblePass(arr, n);
    return swapped ? sort(newArr, n - 1) : newArr;
  };

  // 初始传入的是[...array]，本身就是T[]，直接返回sort结果即可
  return sort([...array], array.length);
}

方案二：安全的类型断言（更简洁） #

如果你不想修改内部函数的类型标注，直接在最后返回时用类型断言即可——因为sort返回的ReadonlyArray<T>实际上是普通数组实例（所有内部创建的数组都是通过[...arr]生成的），所以断言为T[]是完全安全的：

export default function bubbleSort<T>(array: ReadonlyArray<T>, compare: (a: T, b: T) => number): T[] {
  // 保留你原来的内部函数实现，只修改最后一行
  const swap = (arr: ReadonlyArray<T>, i: number, j: number): ReadonlyArray<T> => {
    const newArr = [...arr];
    [newArr[i], newArr[j]] = [newArr[j], newArr[i]];
    return newArr;
  };

  const bubblePass = (arr: ReadonlyArray<T>, n: number): [ReadonlyArray<T>, boolean] => {
    return arr.slice(1, n).reduce(
      ([accArray, swapped], _, i) => {
        if (compare(accArray[i], accArray[i + 1]) > 0) {
          return [swap(accArray, i, i + 1), true];
        }
        return [accArray, swapped];
      },
      [arr, false] as [ReadonlyArray<T>, boolean],
    );
  };

  const sort = (arr: ReadonlyArray<T>, n: number): ReadonlyArray<T> => {
    if (n <= 1) return arr;
    const [newArr, swapped] = bubblePass(arr, n);
    return swapped ? sort(newArr, n - 1) : newArr;
  };

  // 用类型断言替代slice()，去掉多余复制
  return sort([...array], array.length) as T[];
}

为什么这两种方案可行？ #

• 函数式不可变性要求的是不修改输入数组，而内部创建的新数组本身可以是可变类型——我们只是在排序过程中不修改这些新数组，而是每次返回新的副本，完全符合不可变原则。
• 类型层面上，ReadonlyArray<T>是T[]的父类型，普通数组可以被赋值给ReadonlyArray<T>，但反过来需要断言（因为TS不知道你不会修改它），而我们这里明确知道返回的数组是新创建的，不会被内部修改，所以断言是安全的。

内容的提问来源于stack exchange，提问作者Tom Fan