写在前面 本文执行环境typescript，版本4.7.4
元组快排
能否将元组 [3, 1, 2, 4] 通过泛型转换成 [1, 2, 3, 4]
如何实现快排？
• 遍历元组
• 元组每个值的大小比较
• 每次比较中挑选出符合条件的值，也就是实现 Filter
实现逻辑
数字的大小比较
在typescript类型中没有比较符，蓝狮注册开户那如何判断 5 和 6 谁更大？
typescript类型不知道，所以需要找到在typescript中已经存在的递增数列，通过这个数列来实现
怎么理解呢
类似有 张三 和 李四 两个人，要比较他们谁的位置靠前，需要有一个他们排队的数列，然后依次查看，先看到 张三，那么 张三 的位置明显靠前
typescript中有这样的递增数列吗？
有的：元组下标（取元祖长度，元祖push的时候长度是递增的数列），只需要递归元组，就可以实现依次点名
A 是否 小于或等于 B
• 无限递归，直到匹配到 A 或者 B
• 先匹配到 A 返回true（表示A小于或等于B），否则返回false
type SmallerThan<
A extends number,
B extends number,
T extends number[] = []
= T[‘length’] extends A ? true :
T[‘length’] extends B ? false :
SmallerThan;
A 是否 大于或等于 B
逻辑同理
• 无限递归，直到匹配到 A 或者 B
• 先匹配到 A 返回false，否则返回true（表示A大于或等于B）
type LargerThan<
A extends number,
B extends number,
T extends number[] = []
= T[‘length’] extends A ? false :
T[‘length’] extends B ? true :
LargerThan;
当然也可以依赖 SmallerThan 泛型来实现
• 与SmallerThan的布尔值取反
type LargerThan<
A extends number,
B extends number,
T extends number[] = []
= SmallerThan extends true ? false : true;
Filter
• 根据元组长度递归，直到递归次数与元祖长度相等
• 当满足条件（比如：大于等于某个值），将值存储到新元组中，否则不操作
• 依赖上面实现的大小值比较 分别实现 对应的Filter
基于已有的 LargerThan 泛型实现 FilterLargerThan
type FilterLargerThan<
T extends number[],
A extends number,
Z extends number[] = [],
R extends number[] = []
= T[‘length’] extends R[‘length’] ?
Z : FilterLargerThan< T, A, LargerThan extends true ? […Z, T[R[‘length’]]] : Z,
[…R, 0]
;
同理，基于已有的 SmallerThan 泛型实现 FilterSmallerThan
type FilterSmallerThan<
T extends number[],
A extends number,
Z extends number[] = [],
R extends number[] = []
= T[‘length’] extends R[‘length’] ?
Z : FilterSmallerThan< T, A, SmallerThan extends true ? […Z, T[R[‘length’]]] : Z,
[…R, 0]
;
优化Filter
Filter写的很重复了，根据DRY原则（don’t repeat yourself），需要将泛型作为参数传进去，来避免冗余重复的代码
重构数字的大小值比较
如何把泛型作为参数传入，然后在参数中限定？
嗯…好问题
// 目标是实现这种
type Test = T;
貌似不太行，那变个思路：
实现一个泛型对象，每个键值对实现对应的处理，最后只需要传入这个对象的key来获取泛
型，在参数的限定可以变成对key的限定，通过keyof 对象即可实现
• 实现一个泛型对象Demo
• 每个键值对实现对应的处理，如 a: F
• 传入这个对象的key来获取泛型，如 T extends keyof Demo
type t1 = Test<1, ‘a’>;
• 根据上述原则，将对应的泛型组合成泛型对象 Compare
• SmallerThan 实现之前的 SmallerThan 泛型
• LargerThan 实现之前的 LargerThan 泛型
type Compare = {
[‘SmallerThan’]:
T[‘length’] extends A ? true :
T[‘length’] extends B ? false :
Compare[‘SmallerThan’];
['LargerThan']:
T['length'] extends A ? false :
T['length'] extends B ? true :
Compare<A, B, [...T, 0]>['LargerThan'];}
重构Filter
• 将对应的泛型改成 Compare
• key需要手动传入，即为字符串 SmallerThan 和 LargerThan
type Filter< T extends number[], A extends number, key extends keyof Compare,
Z extends number[] = [],
R extends number[] = [],
= T[‘length’] extends R[‘length’] ?
Z : Filter< T, A, key, Compare[key] extends true ? […Z, T[R[‘length’]]] : Z,
[…R, 0]
;
快排
• 递归元组，直到拆解为长度 0 或者 1 的元祖
• 元组长度小于等于 1 的时候返回自身
• 默认取第一项作为对比值，并用泛型 UNSHIFT 移除第一项
• 通过filter和第一项比较筛选出对应的新元祖
type UNSHIFT = T extends [number, …infer U] ? U: [];
// 确保 Smaller 和 Larger 为元祖/数组
type IsArray = T extends number[] ? T : [];
// 快排
type QuickSort< T extends number[], Smaller extends number[] = IsArray, T[0], ‘SmallerThan’>>,
Larger extends number[] = IsArray, T[0], ‘LargerThan’>>
= T[‘length’] extends 0 | 1 ?
T : [
…QuickSort,
T[0],
…QuickSort
];
测试快排
type ARR1 = [5, 2, 4, 1, 0, 6];
type test1 = QuickSort;
// [0, 1, 2, 4, 5, 6]
type ARR2 = [3, 2, 7, 1, 0, 6, 9, 5, 8, 4];
type test2 = QuickSort;
// [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
type ARR3 = [1, 1, 0, 1, 1, 0, 0];
type test3 = QuickSort;
// [0, 0, 0, 1, 1, 1, 1]
看起来一切正常，可以发现遗漏了负数
测试负数的时候问题出现了
因为最开始的大小值对比，是从0开始无限递归的
结束条件是命中其中一个数，然而负数是永远不会命中，蓝狮注册登陆这就是致命bug！
优化：负数
负数的判断
负数的特点：多了一个符号，也就是 “-“
• 转换成字符串后取第一个字符判断是否为 “-“
• 通过 infer 来获取第一个字符
type isFuShu = ${T} extends ${infer P}${string} ?
P extends ‘-‘ : true : false;
type i1 = isFuShu<6>; // false
type i2 = isFuShu<-6>; // true
字符串转数字
但是这样拿到的是字符串，还要把字符串转成数字
和大小比较的逻辑一样
• 无限递归，每次递归传入新元组
• 元组长度（模板字符串） 等于 参数后结束递归，并返回元组长度
type ToNumber =
S extends ${R['length']} ?
R[‘length’] : ToNumber;
获取负数的值
判断是负数后要拿到负数的值 • 和负数符号判断类似，获取除开符号之后的字符串 • 字符串通过泛型 ToNumber 转数字
0 Comments