使用typescript类型来实现快排详情
作者:东东么么哒 时间:2024-06-05 09:13:15
前言
本文执行环境typescript,版本4.7.4
不使用typescript的计算能力,通过类型来实现快排
元组快排
能否将元组 [3, 1, 2, 4] 通过泛型转换成 [1, 2, 3, 4]
如何实现快排?
遍历元组
元组每个值的大小比较
每次比较中挑选出符合条件的值,也就是实现 Filter
实现逻辑
实现数字的大小比较
在typescript类型中没有比较符,那如何判断 5 和 6 谁更大?
typescript类型不知道,所以需要找到在typescript中已经存在的递增数列,通过这个数列来实现
怎么理解呢?
类似有 张三 和 李四 两个人,要比较他们谁的位置靠前,需要有一个他们排队的数列,然后依次查看,先看到 张三,那么 张三 的位置明显靠前
typescript中有这样的递增数列吗?
有的:元组下标,只需要递归元组,就可以实现依次点名
实现 A 是否 小于或等于 B
无限递归,直到匹配到 A 或者 B
type SmallerThan<
A extends number,
B extends number,
T extends number[] = []
> = T['length'] extends A ? true :
T['length'] extends B ? false :
SmallerThan<A, B, [...T, 0]>;
实现 A 是否 大于或等于 B
逻辑同理:
无限递归,直到匹配到 A 或者 B
type LargerThan<
A extends number,
B extends number,
T extends number[] = []
> = T['length'] extends A ? false :
T['length'] extends B ? true :
LargerThan<A, B, [...T, 0]>;
当然也可以依赖 SmallerThan 泛型来实现
type LargerThan<
A extends number,
B extends number,
T extends number[] = []
> = SmallerThan<A, B, T> extends true ? false : true;
实现Filter
根据元组长度递归
当满足条件(比如:大于等于 一个值),将值存储到新元组中,否则不操作
依赖上面实现的大小值比较 分别实现 对应的Filter
type FilterLargerThan<
T extends number[],
A extends number,
Z extends number[] = [],
R extends number[] = []
> = T['length'] extends R['length'] ?
Z : FilterLargerThan<
T,
A,
LargerThan<T[R['length']], A> extends true ? [...Z, T[R['length']]] : Z,
[...R, 0]
>;
type FilterSmallerThan<
T extends number[],
A extends number,
Z extends number[] = [],
R extends number[] = []
> = T['length'] extends R['length'] ?
Z : FilterSmallerThan<
T,
A,
SmallerThan<T[R['length']], A> extends true ? [...Z, T[R['length']]] : Z,
[...R, 0]
>;
优化Filter
Filter写的很重复了,将泛型作为参数传进去
重构数字的大小值比较
如何把泛型作为参数传入,然后在参数中限定...好问题
// 目标是实现这种
type Test<A extends number, T extends ?> = T<A>;
貌似不太行,那变个思路:
实现一个对象,每个键值对实现一个泛型,最后只需要传入这个对象的key来获取泛型,在参数的限定可以变成对key的限定,通过keyof 对象即可实现
type F<A extends number> = A;
type Demo<A extends number> = {
a: F<A>;
}
type Test<A extends number, T extends keyof Demo<number>> = Demo<A>[T];
type t1 = Test<1, 'a'>;
复用逻辑,将对应的泛型改成键值对
type Compare<A extends number, B extends number, T extends number[] = []> = {
['SmallerThan']:
T['length'] extends A ? true :
T['length'] extends B ? false :
Compare<A, B, [...T, 0]>['SmallerThan'];
['LargerThan']:
T['length'] extends A ? false :
T['length'] extends B ? true :
Compare<A, B, [...T, 0]>['LargerThan'];
}
重构Filter
复用逻辑,将对应的泛型改成键值对,key需要手动传入
type Filter<
T extends number[],
A extends number,
key extends keyof Compare<number, number>,
Z extends number[] = [],
R extends number[] = [],
> = T['length'] extends R['length'] ?
Z : Filter<
T,
A,
key,
Compare<T[R['length']], A>[key] extends true ? [...Z, T[R['length']]] : Z,
[...R, 0]
>;
实现快排
递归元组
元组长度小于等于1的时候返回自身
默认取第一项作为对比值
递归的参数通过filter和第一项比较
type UNSHIFT<T extends number[]> = T extends [number, ...infer U] ? U: [];
// 快排
type QuickSort<T extends any[]> = T['length'] extends 0 | 1 ?
T : [
...QuickSort<Filter<UNSHIFT<T>, T[0], 'SmallerThan'>>,
T[0],
...QuickSort<Filter<UNSHIFT<T>, T[0], 'LargerThan'>>
];
测试快排
type ARR1 = [5, 2, 4, 1, 0, 6];
type test1 = QuickSort<ARR1>;
// [0, 1, 2, 4, 5, 6]
type ARR2 = [3, 2, 7, 1, 0, 6, 9, 5, 8, 4];
type test2 = QuickSort<ARR2>;
// [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
type ARR3 = [1, 1, 0, 1, 1, 0, 0];
type test3 = QuickSort<ARR3>;
// [0, 0, 0, 1, 1, 1, 1]
看起来一切正常,可以发现遗漏了负数
测试负数的时候问题出现了
因为最开始的大小值对比,是从0开始无限递归的
结束条件是命中其中一个数,然而负数是永远不会命中,这就是致命bug!
优化:负数
负数的判断
负数的特点:多了一个符号,也就是 '-',转换成字符串后拿第一个字符判断
type isFuShu<T extends number> = `${T}` extends `${infer P}${string}` ?
P extends '-' : true : false;
type i1 = isFuShu<6>; // false
type i2 = isFuShu<-6>; // true
字符串转数字
但是这样拿到的是字符串,还要把字符串转成数字
和大小比较的逻辑一样
无限递归,每次循环创建新元组
元组长度(模板字符串) 等于 参数后结束递归,并返回元组长度
type ToNumber<S extends string, R extends number[] = []> =
S extends `${R['length']}` ?
R['length'] : ToNumber<S, [...R, 0]>;
获取负数的值
判断是负数后要拿到负数的值
和负数符号判断类似,获取除开符号之后的字符串,转数字
type GetFushu<T extends number> = `${T}` extends `${string}${infer U}` ?
ToNumber<U> : 0;
完善获取绝对值
type GetAbs<T extends number> = isFuShu<T> extends true ? GetFushu<T> : T;
重构数字的大小比较
负数的对比和正数相反,且正数一定比负数大
非负数数直接比较
负数取反比较
非负数一定大于负数
type CompareV2<A extends number, B extends number, T extends number[] = []> = {
['SmallerThan']:
T['length'] extends A ? true :
T['length'] extends B ? false :
CompareV2<GetAbs<A>, GetAbs<B>, [...T, 0]>['SmallerThan'];
['SmallerThanV2']:
isFuShu<A> extends true ?
(isFuShu<B> extends true ?
CompareV2<A, B>['LargerThan'] :
true) :
(isFuShu<B> extends true ?
false :
CompareV2<A, B>['SmallerThan']);
['LargerThan']:
T['length'] extends A ? false :
T['length'] extends B ? true :
CompareV2<GetAbs<A>, GetAbs<B>, [...T, 0]>['LargerThan'];
['LargerThanV2']:
isFuShu<A> extends true ?
(isFuShu<B> extends true ?
CompareV2<A, B>['SmallerThan'] :
false) :
(isFuShu<B> extends true ?
true :
CompareV2<A, B>['LargerThan']);
}
测试用例:
type h1 = CompareV2<-8, -6>['SmallerThanV2']; // true
type h2 = CompareV2<8, -6>['SmallerThanV2']; // false
type h3 = CompareV2<6, 8>['SmallerThanV2']; // true
type h4 = CompareV2<-8, 6>['SmallerThanV2']; // true
type i1 = CompareV2<-8, -6>['LargerThanV2']; // false
type i2 = CompareV2<8, -6>['LargerThanV2']; // true
type i3 = CompareV2<6, 8>['LargerThanV2']; // false
type i4 = CompareV2<-8, 6>['LargerThanV2']; // false
重构快排
更换重构的泛型
type FilterV2<
T extends number[],
A extends number,
key extends keyof CompareV2<number, number>,
Z extends number[] = [],
R extends number[] = [],
> = T['length'] extends R['length'] ?
Z : FilterV2<
T,
A,
key,
CompareV2<T[R['length']], A>[key] extends true ? [...Z, T[R['length']]] : Z,
[...R, 0]
>;
// 快排
type QuickSortV2<T extends any[]> = T['length'] extends 0 | 1 ?
T : [
...QuickSortV2<FilterV2<UNSHIFT<T>, T[0], 'SmallerThanV2'>>,
T[0],
...QuickSortV2<FilterV2<UNSHIFT<T>, T[0], 'LargerThanV2'>>
];
测试快排V2
type ARR4 = [-5, -2, -4, -1, 0, -6];
type test4 = QuickSortV2<ARR4>;
// [-6, -5, -4, -2, -1, 0]
type ARR5 = [-5, -2, 4, -1, 0, -6, 2, -3, 7];
type test5 = QuickSortV2<ARR5>;
// [-6, -5, -3, -2, -1, 0, 2, 4, 7]
type ARR6 = [3, -2, 7, -1, 0, -6, 9, -5, 8, -4];
type test6 = QuickSortV2<ARR6>;
// [-6, -5, -4, -2, -1, 0, 3, 7, 8, 9]
来源:https://juejin.cn/post/7130525674376265741
![](/images/zang.png)
![](/images/jiucuo.png)
猜你喜欢
python自定义函数实现最大值的输出方法
浅谈python日志的配置文件路径问题
Python如何使用Gitlab API实现批量的合并分支
Python selenium键盘鼠标事件实现过程详解
sqlserver下Kill 所有连接到某一数据库的连接
asp自带的内存缓存 application
Python与AI分析时间序列数据
![](https://img.aspxhome.com/file/2023/2/104872_0s.jpg)
Pytorch 中net.train 和 net.eval的使用说明
使用Python编写提取日志中的中文的脚本的方法
![](https://img.aspxhome.com/file/2023/9/81849_0s.png)
element-ui中实现tree子节点部分选中时父节点也选中
![](https://img.aspxhome.com/file/2023/1/130101_0s.png)
Numpy对数组的操作:创建、变形(升降维等)、计算、取值、复制、分割、合并
javascript实现下雪效果【实例代码】
详解Python flask的前后端交互
![](https://img.aspxhome.com/file/2023/0/117420_0s.png)
Vue使用localStorage存储数据的方法
![](https://img.aspxhome.com/file/2023/5/130245_0s.png)
基于vue v-for 循环复选框-默认勾选第一个的实现方法
Python编程之多态用法实例详解
PyQt5每天必学之单行文本框
![](https://img.aspxhome.com/file/2023/1/82551_0s.png)
Python3 webservice接口测试代码详解
python的pip安装以及使用教程
![](https://img.aspxhome.com/file/2023/9/72919_0s.png)