TypeScript 杂记五《Sort》

说明

Sort

Sort<[]> // []
Sort<[1]> // [1]
Sort<[2, 4, 7, 6, 6, 6, 5, 8, 9]> //  [2, 4, 5, 6, 6, 6, 7, 8, 9]
Sort<[3, 2, 1], true> // [3, 2, 1]
Sort<[3, 2, 0, 1, 0, 0, 0], true> // [3, 2, 1, 0, 0, 0, 0]

扩展：支持 bigint 和 float

思路

先实现简单的整数，大致如下：

type IType = number;
type Sort<T extends IType[]> = Helper<T>;

默认升序，第二参数可以改成降序，大致如下：

type Reverse<T extends unknown[], RR extends unknown[] = []> = T extends [
  ...infer L,
  infer R
]
  ? Reverse<L, [...RR, R]>
  : RR;

type Sort<T extends IType[], D extends boolean = false> = D extends false
  ? Helper<T>
  : Reverse<Helper<T>>;

只有数据长度大于 1 的时候才会触发排序，大致如下：

type Helper<T extends IType[]> = T extends [] | [IType] ? T : Run<T>;

这里采用冒泡排序的方式（实现简单），大致如下：
- Compare 用来比较两个数字的大小。返回 1 表示 B 小，则需要交换
- 每次获取数组的前两个进行比较，小的那个写入 R 中。大的继续下一次的运行
- 如果本次递归中发生过交换，那么重新执行一次，这个时候新的数据就是上一次的结果
- 直到没有发生过交换则返回结果

type Run<
  T extends unknown[],
  R extends unknown[] = [],
  F extends boolean = false
> = T extends [infer A, infer B, ...infer C]
  ? Run<
      [Compare<A, B> extends 1 ? A : B, ...C],
      [...R, Compare<A, B> extends 1 ? B : A],
      F extends true ? F : Compare<A, B> extends 1 ? true : false
    >
  : F extends true
  ? Run<[...R, T[0]]>
  : [...R, T[0]];

比较函数的实现
- 如果两个数字是负数，则取整数部分比较，结果取反
- 如果两个数字是正数，则直接比较
- 如果 A 是负数，返回 -1
- 如果 B 是负数，返回 1

type Compare<A, B> = A extends IType
  ? B extends IType
    ? `${A}` extends `-${infer AA}`
      ? `${B}` extends `-${infer BB}`
        ? CompareHelper<AA, BB> extends 1
          ? -1
          : CompareHelper<AA, BB> extends 0
          ? 0
          : 1
        : -1
      : `${B}` extends `-${infer BB}`
      ? 1
      : CompareHelper<`${A}`, `${B}`>
    : -1
  : -1;

实现具体的比较：
- H 的长度同时等于 A，B 则表示两个相等，返回 0
- H 先等于 A，说明 A 大，返回 1
- H 先等于 B，说明 B 大，返回 -1

type CompareHelper<
  A extends string,
  B extends string,
  H extends unknown[] = []
> = `${H["length"]}` extends B
  ? `${H["length"]}` extends A
    ? 0
    : 1
  : `${H["length"]}` extends A
  ? -1
  : CompareHelper<A, B, [...H, unknown]>;

最终结果

type IType = number;

type Reverse<T extends unknown[], RR extends unknown[] = []> = T extends [
  ...infer L,
  infer R
]
  ? Reverse<L, [...RR, R]>
  : RR;

type CompareHelper<
  A extends string,
  B extends string,
  H extends unknown[] = []
> = `${H["length"]}` extends B
  ? `${H["length"]}` extends A
    ? 0
    : 1
  : `${H["length"]}` extends A
  ? -1
  : CompareHelper<A, B, [...H, unknown]>;

type Compare<A, B> = A extends IType
  ? B extends IType
    ? `${A}` extends `-${infer AA}`
      ? `${B}` extends `-${infer BB}`
        ? CompareHelper<AA, BB> extends 1
          ? -1
          : CompareHelper<AA, BB> extends 0
          ? 0
          : 1
        : -1
      : `${B}` extends `-${infer BB}`
      ? 1
      : CompareHelper<`${A}`, `${B}`>
    : -1
  : -1;

type Run<
  T extends unknown[],
  R extends unknown[] = [],
  F extends boolean = false
> = T extends [infer A, infer B, ...infer C]
  ? Run<
      [Compare<A, B> extends 1 ? A : B, ...C],
      [...R, Compare<A, B> extends 1 ? B : A],
      F extends true ? F : Compare<A, B> extends 1 ? true : false
    >
  : F extends true
  ? Run<[...R, T[0]]>
  : [...R, T[0]];

type Helper<T extends IType[]> = T extends [] | [IType] ? T : Run<T>;

type Sort<T extends IType[], D extends boolean = false> = D extends false
  ? Helper<T>
  : Reverse<Helper<T>>;

type Test1 = Sort<[]>; // []
type Test2 = Sort<[1]>; // [1]
type Test3 = Sort<[2, 4, 7, 6, 6, 6, 5, 8, 9]>; //  [2, 4, 5, 6, 6, 6, 7, 8, 9]
type Test4 = Sort<[3, 2, 1], true>; // [3, 2, 1]
type Test5 = Sort<[3, 2, 0, 1, 0, 0, 0], true>; // [3, 2, 1, 0, 0, 0, 0]
type Test6 = Sort<[2, -4, 7, 6, -6, 6, 5, 8, 9]>; // [-6, -4, 2, 5, 6, 6, 7, 8, 9]
type Test7 = Sort<[2, -4, 7, 6, -6, 6, 5, 8, 9], true>; // [9, 8, 7, 6, 6, 5, 2, -4, -6]

扩展 - bigint

首先将数字转换成字符串数组，大致如下：

type IType = number | bigint;

type StringToArray<
  T,
  RR extends string[] = []
> = T extends `${infer L}${infer R}` ? StringToArray<R, [...RR, L]> : RR;

// 这里改造一下，应为已经提前处理了负数，所以这里只会是正数
type Compare<A, B> = A extends string
  ? B extends string
    ? CompareHelper<A, B>
    : -1
  : -1;

type CompareArray<A, B> = A extends IType
  ? B extends IType
    ? `${A}` extends `-${infer AA}`
      ? `${B}` extends `-${infer BB}`
        ? CompareArrayHelper<StringToArray<AA>, StringToArray<BB>> extends 1
          ? -1
          : CompareArrayHelper<StringToArray<AA>, StringToArray<BB>> extends 0
          ? 0
          : 1
        : -1
      : `${B}` extends `-${infer BB}`
      ? 1
      : CompareArrayHelper<StringToArray<`${A}`>, StringToArray<`${B}`>>
    : -1
  : -1;

比较两个数组
- 如果 A 的长度大于 B 则返回 -1
- 如果 B 的长度大于 A 则返回 1
- 长度一致，则从头开始比较两个数组的每一项
- 这里改造之前的结果

type CompareArrayHelper<
  A extends string[],
  B extends string[],
  H extends unknown[] = []
> = H["length"] extends B["length"]
  ? H["length"] extends A["length"]
    ? CompareArrayHelperEqual<A, B>
    : 1
  : H["length"] extends A["length"]
  ? -1
  : CompareArrayHelper<A, B, [...H, unknown]>;

比较数组的每一项
- 如果返回 0，则比较下一个数字
- 否则返回 Compare 的值
- 如果一直到结果都是没有返回结果则表示相等，返回 0

type CompareArrayHelperEqual<
  A extends unknown[],
  B extends unknown[]
> = A extends [infer AL, ...infer AR]
  ? B extends [infer BL, ...infer BR]
    ? Compare<AL, BL> extends 0
      ? CompareArrayHelperEqual<AR, BR>
      : Compare<AL, BL>
    : 0
  : 0;

优化后的结果：

type IType = number | bigint;

type Reverse<T extends unknown[], RR extends unknown[] = []> = T extends [
  ...infer L,
  infer R
]
  ? Reverse<L, [...RR, R]>
  : RR;

type StringToArray<
  T extends string,
  RR extends string[] = []
> = T extends `${infer L}${infer R}` ? StringToArray<R, [...RR, L]> : RR;

type CompareHelper<
  A extends string,
  B extends string,
  H extends unknown[] = []
> = `${H["length"]}` extends B
  ? `${H["length"]}` extends A
    ? 0
    : 1
  : `${H["length"]}` extends A
  ? -1
  : CompareHelper<A, B, [...H, unknown]>;

type Compare<A, B> = A extends string
  ? B extends string
    ? CompareHelper<A, B>
    : -1
  : -1;

type CompareArrayHelperEqual<
  A extends unknown[],
  B extends unknown[]
> = A extends [infer AL, ...infer AR]
  ? B extends [infer BL, ...infer BR]
    ? Compare<AL, BL> extends 0
      ? CompareArrayHelperEqual<AR, BR>
      : Compare<AL, BL>
    : 0
  : 0;

type CompareArrayHelper<
  A extends string[],
  B extends string[],
  H extends unknown[] = []
> = H["length"] extends B["length"]
  ? H["length"] extends A["length"]
    ? CompareArrayHelperEqual<A, B>
    : 1
  : H["length"] extends A["length"]
  ? -1
  : CompareArrayHelper<A, B, [...H, unknown]>;

type CompareArray<A, B> = A extends IType
  ? B extends IType
    ? `${A}` extends `-${infer AA}`
      ? `${B}` extends `-${infer BB}`
        ? CompareArrayHelper<StringToArray<AA>, StringToArray<BB>> extends 1
          ? -1
          : CompareArrayHelper<StringToArray<AA>, StringToArray<BB>> extends 0
          ? 0
          : 1
        : -1
      : `${B}` extends `-${infer BB}`
      ? 1
      : CompareArrayHelper<StringToArray<`${A}`>, StringToArray<`${B}`>>
    : -1
  : -1;

type Run<
  T extends unknown[],
  R extends unknown[] = [],
  F extends boolean = false
> = T extends [infer A, infer B, ...infer C]
  ? Run<
      [CompareArray<A, B> extends 1 ? A : B, ...C],
      [...R, CompareArray<A, B> extends 1 ? B : A],
      F extends true ? F : CompareArray<A, B> extends 1 ? true : false
    >
  : F extends true
  ? Run<[...R, T[0]]>
  : [...R, T[0]];

type Helper<T extends IType[]> = T extends [] | [IType] ? T : Run<T>;

type Sort<T extends IType[], D extends boolean = false> = D extends false
  ? Helper<T>
  : Reverse<Helper<T>>;

type Test1 = Sort<[]>; // []
type Test2 = Sort<[1]>; // [1]
type Test3 = Sort<[2, 4, 7, 6, 6, 6, 5, 8, 9]>; //  [2, 4, 5, 6, 6, 6, 7, 8, 9]
type Test4 = Sort<[3, 2, 1], true>; // [3, 2, 1]
type Test5 = Sort<[3, 2, 0, 1, 0, 0, 0], true>; // [3, 2, 1, 0, 0, 0, 0]
type Test6 = Sort<[2, -4, 7, 6, -6, 6, 5, 8, 9]>; // [-6, -4, 2, 5, 6, 6, 7, 8, 9]
type Test7 = Sort<[2, -4, 7, 6, -6, 6, 5, 8, 9], true>; // [9, 8, 7, 6, 6, 5, 2, -4, -6]
type Test8 = Sort<
  [
    1_000_000_000_000n,
    2_000_000_000_000n,
    1_030_000_000_000n,
    -4,
    7,
    6,
    -6,
    6,
    5,
    8,
    9
  ]
>; // [-6, -4, 5, 6, 6, 7, 8, 9, 1000000000000n, 1030000000000n, 2000000000000n]
type Test9 = Sort<
  [
    1_000_000_000_000n,
    2_000_000_000_000n,
    1_030_000_000_000n,
    -1_000_000_000_000n,
    -2_000_000_000_000n,
    -1_030_000_000_000n,
    -4,
    7,
    6,
    -6,
    6,
    5,
    8,
    9
  ]
>; // [-2000000000000n, -1030000000000n, -1000000000000n, -6, -4, 5, 6, 6, 7, 8, 9, 1000000000000n, 1030000000000n, 2000000000000n]

扩展 - float

我们把所有输入的数据都认为是浮点型，如果是整数则我们用 0 表示其对应的小数部分

type CompareArrayFloat<A, B> = A extends IType
  ? B extends IType
    ? `${A}` extends `${infer AL}.${infer AR}`
      ? `${B}` extends `${infer BL}.${infer BR}`
        ? CompareArrayFloatHelper<AL, AR, BL, BR>
        : CompareArrayFloatHelper<AL, AR, B, "0">
      : `${B}` extends `${infer BL}.${infer BR}`
      ? CompareArrayFloatHelper<A, "0", BL, BR>
      : CompareArrayFloatHelper<A, "0", B, "0">
    : -1
  : -1;

具体的比较
- 先比较整数部分，如果返回结果不等于 0，则直接返回具体的值
- 否则，我们就去比较小数部分

type CompareArrayFloatHelper<AL, AR, BL, BR> = CompareArray<AL, BL> extends 0
  ? CompareArray<AR, BR>
  : CompareArray<AL, BL>;

小数的比较我们需要有个额外的特殊处理，将长度小的数字用 0 补齐，是两个数字长度一致。例如：0.1000 和 0.0001。我们比较的是 1000 和 0001

type ArrayToString<T extends unknown[]> = T extends [infer L, ...infer R]
  ? L extends string
    ? `${L}${ArrayToString<R>}`
    : ""
  : "";

type CompareArrayFullZero<
  A extends unknown[],
  B extends unknown[],
  H extends unknown[] = []
> = H["length"] extends A["length"]
  ? H["length"] extends B["length"]
    ? CompareArray<ArrayToString<A>, ArrayToString<B>>
    : CompareArrayFullZero<[...A, "0"], B, H>
  : H["length"] extends B["length"]
  ? CompareArrayFullZero<A, [...B, "0"], H>
  : CompareArrayFullZero<A, B, [...H, unknown]>;

type CompareArrayFloatHelper<AL, AR, BL, BR> = CompareArray<AL, BL> extends 0
  ? CompareArrayFullZero<StringToArray<AR>, StringToArray<BR>>
  : CompareArray<AL, BL>;

此时 CompareArray 接受的可能都是字符串，所以需要改变一下

type CompareArray<A, B> = A extends IType | string
  ? B extends IType | string
    ? `${A}` extends `-${infer AA}`
      ? `${B}` extends `-${infer BB}`
        ? CompareArrayHelper<StringToArray<AA>, StringToArray<BB>> extends 1
          ? -1
          : CompareArrayHelper<StringToArray<AA>, StringToArray<BB>> extends 0
          ? 0
          : 1
        : -1
      : `${B}` extends `-${infer BB}`
      ? 1
      : CompareArrayHelper<StringToArray<`${A}`>, StringToArray<`${B}`>>
    : -1
  : -1;

还有一点如果整数部分返回 0 ，这个时候要比较小数，如果正数部分是负数，小数的返回结果要取反。（注意：等于 0 ，说明整数部分是一样的）
同时我们写一个辅助函数 ReverseNumber，把之前所有需要反转结果的地方使用这个定义去实现

type ReverseNumber<T> = T extends 1 ? -1 : T extends 0 ? 0 : 1;

type CompareArrayFloatHelper<AL, AR, BL, BR> = CompareArray<AL, BL> extends 0
  ? AL extends `-${infer A}`
    ? ReverseNumber<CompareArrayFullZero<StringToArray<AR>, StringToArray<BR>>>
    : CompareArrayFullZero<StringToArray<AR>, StringToArray<BR>>
  : CompareArray<AL, BL>;

最终结果

type IType = number | bigint;

type Reverse<T extends unknown[], RR extends unknown[] = []> = T extends [
  ...infer L,
  infer R
]
  ? Reverse<L, [...RR, R]>
  : RR;

type ReverseNumber<T> = T extends 1 ? -1 : T extends 0 ? 0 : 1;

type StringToArray<
  T,
  RR extends string[] = []
> = T extends `${infer L}${infer R}` ? StringToArray<R, [...RR, L]> : RR;

type CompareHelper<
  A extends string,
  B extends string,
  H extends unknown[] = []
> = `${H["length"]}` extends B
  ? `${H["length"]}` extends A
    ? 0
    : 1
  : `${H["length"]}` extends A
  ? -1
  : CompareHelper<A, B, [...H, unknown]>;

type Compare<A, B> = A extends string
  ? B extends string
    ? CompareHelper<A, B>
    : -1
  : -1;

type CompareArrayHelperEqual<
  A extends unknown[],
  B extends unknown[]
> = A extends [infer AL, ...infer AR]
  ? B extends [infer BL, ...infer BR]
    ? Compare<AL, BL> extends 0
      ? CompareArrayHelperEqual<AR, BR>
      : Compare<AL, BL>
    : 0
  : 0;

type CompareArrayHelper<
  A extends string[],
  B extends string[],
  H extends unknown[] = []
> = H["length"] extends B["length"]
  ? H["length"] extends A["length"]
    ? CompareArrayHelperEqual<A, B>
    : 1
  : H["length"] extends A["length"]
  ? -1
  : CompareArrayHelper<A, B, [...H, unknown]>;

type CompareArray<A, B> = A extends IType | string
  ? B extends IType | string
    ? `${A}` extends `-${infer AA}`
      ? `${B}` extends `-${infer BB}`
        ? ReverseNumber<
            CompareArrayHelper<StringToArray<AA>, StringToArray<BB>>
          >
        : -1
      : `${B}` extends `-${infer BB}`
      ? 1
      : CompareArrayHelper<StringToArray<`${A}`>, StringToArray<`${B}`>>
    : -1
  : -1;

type ArrayToString<T extends unknown[]> = T extends [infer L, ...infer R]
  ? L extends string
    ? `${L}${ArrayToString<R>}`
    : ""
  : "";

type CompareArrayFullZero<
  A extends unknown[],
  B extends unknown[],
  H extends unknown[] = []
> = H["length"] extends A["length"]
  ? H["length"] extends B["length"]
    ? CompareArray<ArrayToString<A>, ArrayToString<B>>
    : CompareArrayFullZero<[...A, "0"], B, H>
  : H["length"] extends B["length"]
  ? CompareArrayFullZero<A, [...B, "0"], H>
  : CompareArrayFullZero<A, B, [...H, unknown]>;

type CompareArrayFloatHelper<AL, AR, BL, BR> = CompareArray<AL, BL> extends 0
  ? AL extends `-${infer A}`
    ? ReverseNumber<CompareArrayFullZero<StringToArray<AR>, StringToArray<BR>>>
    : CompareArrayFullZero<StringToArray<AR>, StringToArray<BR>>
  : CompareArray<AL, BL>;

type CompareArrayFloat<A, B> = A extends IType
  ? B extends IType
    ? `${A}` extends `${infer AL}.${infer AR}`
      ? `${B}` extends `${infer BL}.${infer BR}`
        ? CompareArrayFloatHelper<AL, AR, BL, BR>
        : CompareArrayFloatHelper<AL, AR, B, "0">
      : `${B}` extends `${infer BL}.${infer BR}`
      ? CompareArrayFloatHelper<A, "0", BL, BR>
      : CompareArrayFloatHelper<A, "0", B, "0">
    : -1
  : -1;

type Run<
  T extends unknown[],
  R extends unknown[] = [],
  F extends boolean = false
> = T extends [infer A, infer B, ...infer C]
  ? Run<
      [CompareArrayFloat<A, B> extends 1 ? A : B, ...C],
      [...R, CompareArrayFloat<A, B> extends 1 ? B : A],
      F extends true ? F : CompareArrayFloat<A, B> extends 1 ? true : false
    >
  : F extends true
  ? Run<[...R, T[0]]>
  : [...R, T[0]];

type Helper<T extends IType[]> = T extends [] | [IType] ? T : Run<T>;

type Sort<T extends IType[], D extends boolean = false> = D extends false
  ? Helper<T>
  : Reverse<Helper<T>>;

type Test1 = Sort<[]>; // []
type Test2 = Sort<[1]>; // [1]
type Test3 = Sort<[2, 4, 7, 6, 6, 6, 5, 8, 9]>; //  [2, 4, 5, 6, 6, 6, 7, 8, 9]
type Test4 = Sort<[3, 2, 1], true>; // [3, 2, 1]
type Test5 = Sort<[3, 2, 0, 1, 0, 0, 0], true>; // [3, 2, 1, 0, 0, 0, 0]
type Test6 = Sort<[2, -4, 7, 6, -6, 6, 5, 8, 9]>; // [-6, -4, 2, 5, 6, 6, 7, 8, 9]
type Test7 = Sort<[2, -4, 7, 6, -6, 6, 5, 8, 9], true>; // [9, 8, 7, 6, 6, 5, 2, -4, -6]
type Test8 = Sort<
  [
    1_000_000_000_000n,
    2_000_000_000_000n,
    1_030_000_000_000n,
    -4,
    7,
    6,
    -6,
    6,
    5,
    8,
    9
  ]
>; // [-6, -4, 5, 6, 6, 7, 8, 9, 1000000000000n, 1030000000000n, 2000000000000n]
type Test9 = Sort<
  [
    1_000_000_000_000n,
    2_000_000_000_000n,
    1_030_000_000_000n,
    -1_000_000_000_000n,
    -2_000_000_000_000n,
    -1_030_000_000_000n,
    -4,
    7,
    6,
    -6,
    6,
    5,
    8,
    9
  ]
>; // [-2000000000000n, -1030000000000n, -1000000000000n, -6, -4, 5, 6, 6, 7, 8, 9, 1000000000000n, 1030000000000n, 2000000000000n]
type Test10 = Sort<[2.1, 4.11, 4.12, 4.09]> // [2.1, 4.09, 4.11, 4.12]
type Test11 = Sort<[2.1, -4.11, -4.12, -4.09]> // [-4.12, -4.11, -4.09, 2.1]