写点什么

用 typescript 类型来实现快排

作者:Java-fenn
  • 2022 年 9 月 14 日
    湖南
  • 本文字数:4115 字

    阅读完需:约 14 分钟

TypeScript 快速排序写在前面 本文执行环境 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, [...T, 0]>;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<A, B, [...T, 0]>;当然也可以依赖 SmallerThan 泛型来实现


• 与 SmallerThan 的布尔值取反


type LargerThan<A extends number,B extends number,T extends number[] = []


= SmallerThan<A, B, T> 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<T[R['length']], A> 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<T[R['length']], A> extends true ? [...Z, T[R['length']]] : Z,[...R, 0];优化 FilterFilter 写的很重复了,根据 DRY 原则(don't repeat yourself),需要将泛型作为参数传进去,来避免冗余重复的代码


重构数字的大小值比较如何把泛型作为参数传入,然后在参数中限定?


嗯...好问题


// 目标是实现这种 type Test<A extends number, T extends ?> = T<A>;貌似不太行,那变个思路:


实现一个泛型对象,每个键值对实现对应的处理,最后只需要传入这个对象的 key 来获取泛


型,在参数的限定可以变成对 key 的限定,通过 keyof 对象即可实现


• 实现一个泛型对象 Demo


• 每个键值对实现对应的处理,如 a: F


• 传入这个对象的 key 来获取泛型,如 T extends keyof Demo


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'>;• 根据上述原则,将对应的泛型组合成泛型对象 Compare


• SmallerThan 实现之前的 SmallerThan 泛型


• LargerThan 实现之前的 LargerThan 泛型


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• 将对应的泛型改成 Compare


• key 需要手动传入,即为字符串 SmallerThan 和 LargerThan


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];快排• 递归元组,直到拆解为长度 0 或者 1 的元祖


• 元组长度小于等于 1 的时候返回自身


• 默认取第一项作为对比值,并用泛型 UNSHIFT 移除第一项


• 通过 filter 和第一项比较筛选出对应的新元祖


type UNSHIFT<T extends number[]> = T extends [number, ...infer U] ? U: [];


// 确保 Smaller 和 Larger 为元祖/数组 type IsArray<T> = T extends number[] ? T : [];


// 快排 type QuickSort<T extends number[],Smaller extends number[] = IsArray<Filter<UNSHIFT<T>, T[0], 'SmallerThan'>>,Larger extends number[] = IsArray<Filter<UNSHIFT<T>, T[0], 'LargerThan'>>


= T['length'] extends 0 | 1 ?T : [...QuickSort<Smaller>,T[0],...QuickSort<Larger>];测试快排 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!


优化:负数负数的判断负数的特点:多了一个符号,也就是 "-"


• 转换成字符串后取第一个字符判断是否为 "-"


• 通过 infer 来获取第一个字符


type isFuShu<T extends number> = ${T} extends ${infer P}${string} ?P extends '-' : true : false;


type i1 = isFuShu<6>; // falsetype i2 = isFuShu<-6>; // true 字符串转数字但是这样拿到的是字符串,还要把字符串转成数字


和大小比较的逻辑一样


• 无限递归,每次递归传入新元组


• 元组长度(模板字符串) 等于 参数后结束递归,并返回元组长度


type ToNumber<S extends string, R extends number[] = []> =S extends ${R['length']} ?R['length'] : ToNumber<S, [...R, 0]>;获取负数的值判断是负数后要拿到负数的值


• 和负数符号判断类似,获取除开符号之后的字符串


• 字符串通过泛型 ToNumber 转数字


type GetFushu<T extends number> = ${T} extends ${string}${infer U} ?ToNumber<U> : 0;完善获取绝对值• 非负数返回自身,负数通过泛型 GetFushu 来获取


type GetAbs<T extends number> = isFuShu<T> extends true ? GetFushu<T> : T;重构数字的大小比较负数的对比和正数相反,且正数一定比负数大


• 判断比较的值是负数还是非负数


• 非负数通过泛型 CompareV2 比较大小


• 负数获取绝对值后,通过泛型 CompareV2 取反比较大小


• 非负数一定大于负数


• 泛型 SmallerThan 实现非负数的比较,泛型 SmallerThanV2 实现负数和非负数的比较


• 泛型 LargerThan 和泛型 LargerThanV2 同理


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']; // truetype h2 = CompareV2<8, -6>['SmallerThanV2']; // falsetype h3 = CompareV2<6, 8>['SmallerThanV2']; // truetype h4 = CompareV2<-8, 6>['SmallerThanV2']; // true


type i1 = CompareV2<-8, -6>['LargerThanV2']; // falsetype i2 = CompareV2<8, -6>['LargerThanV2']; // truetype i3 = CompareV2<6, 8>['LargerThanV2']; // falsetype i4 = CompareV2<-8, 6>['LargerThanV2']; // false 重构快排重构泛型 FilterV2(更换 Compare -> CompareV2)


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[],Smaller extends number[] = IsArray<FilterV2<UNSHIFT<T>, T[0], 'SmallerThanV2'>>,Larger extends number[] = IsArray<FilterV2<UNSHIFT<T>, T[0], 'LargerThanV2'>>


= T['length'] extends 0 | 1 ?T : [...QuickSortV2<Smaller>,T[0],...QuickSortV2<Larger>];测试快排 V2type 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]

用户头像

Java-fenn

关注

需要Java资料或者咨询可加我v : Jimbye 2022.08.16 加入

还未添加个人简介

评论

发布
暂无评论
用typescript类型来实现快排_Java_Java-fenn_InfoQ写作社区