使用Typescript类型实现快排

写在前面本文的执行环境是typescript，版本4.7.4tuplequicksort能否将元组[3,1,2,4]通过泛型转换为[1,2,3,4]如何实现quicksort？?遍历元组?比较元组中每个值的大小?在每次比较中选择符合条件的值，即实现Filter实现逻辑数的大小比较。typescript类型中没有comparator，那怎么判断谁是5和6呢？大？我不知道typescript类型，所以我需要找到typescript中已经存在的增量序列。通过这个序列怎么理解呢？类似于张三和李四。要比较它们中的哪一个更高，您需要将其中一个排成一行。sequence，然后一个一个的看，先看到张三，然后张三的位置明显在前面打字有这种递增的顺序吗？有：元组下标（取元组长度，推元组时元组长度为递增序列），只需要递归元组即可实现A是否小于等于B?无限递归直到匹配到A或B?如果先匹配到A返回真（表示A小于等于B），否则返回假类型SmallerThan=T['length']延伸A?真：T['length']扩展了B？false:SmallerThan;A是否大于等于B是同一个逻辑?无限递归直到匹配到A或B?匹配到第一个A返回false，否则返回true（说明A大于等于B）typeLargerThan=T['length']extendsA?false:T['length']扩展B?真:LargerThan;当然也可以依赖SmallerThan泛型来实现?取反SmallerThan类型Larg的boolean值erThan=SmallerThanextendstrue?false:true;Filter根据元组的长度递归，直到递归的次数等于元组的长度?当条件满足时（例如：大于等于某个值），将值存入anewtuple，否则无操作?依赖上面实现的大小值比较，基于现有的LargerThan泛型实现FilterLargerThantypeFilterLargerThan=T['length']extendsR['length']?Z:FilterLargerThanextendstrue?[...Z,T[R['长度']]]:Z,[...R,0]>;同样，基于现有的SmallerThan泛型实现FilterSmallerThantypeFilterSmallerThan=T['length']extendsR['长度']？Z:FilterSmallerThanextendstrue?[...Z,T[R['长度']]]:Z,[...R,0]>;优化FilterFilter是非常重复的。根据DRY原则（不要重复自己），需要将泛型作为参数传入，避免代码冗余和重复。重构数字的大小和值。如何使用泛型作为传入的参数，然后在参数中限定？嗯...好问题//目标是实现这个类型Test=T;好像不行，所以换个思路：实现一个泛型对象，每个键值对实现对应的处理，最后只需要传入这个对象的key就可以得到泛型。参数限制可以改为key限制，可以通过keyof对象来实现?实现一个泛型对象Demo?每个键值对实现相应的处理，比如a:F?传入这个对象的key即可得到泛型类型，例如TextendskeyofDemotypeF=A;typeDemo={a:F;}typeTest>=演示[T];类型t1=测试<1,'a'>;泛型对象Compare?SmallerThan实现了之前的SmallerThan泛型?LargerThan实现了之前的LargerThan泛型类型Compare={['SmallerThan']:T['length']延伸A？真：T['length']扩展了B？false:比较['SmallerThan'];['LargerThan']:T['length']扩展A?错误的:T['length']延伸B?true:Compare['LargerThan'];}重构Filter?将对应的泛型改为Compare?key需要手动传入，即字符串SmallerThan和LargerThantypeFilter,Zextendsnumber[]=[],Rextendsnumber[]=[],>=T['length']extendsR['长度']？Z:Filter[key]extendstrue?[...Z,T[R['length']]]:Z,[...R,0]>;Quicksort?递归递归元组，直到它被分解为长度为0或1的元组?长度为小于等于1返回自身时?默认取第一项作为比较值，泛型UNSHIFT去除第一项?通过与第一项类型UNSHIFT比较过滤器过滤掉对应的新祖先=Textends[number,...inferU]?U:[];//确保Smaller和Larger是元组/数组类型IsArray=Textendsnumber[]?T:[];//快速排序类型QuickSort,T[0],'SmallerThan'>>,Largerextendssnumber[]=IsArray,T[0],'LargerThan'>>>=T['length']extends0|1？T:[...QuickSort,T[0],...QuickSort];测试快速排序类型ARR1=[5,2,4,1,0,6];typetest1=QuickSort;//[0,1,2,4,5,6]typeARR2=[3,2,7,1,0,6,9,5,8,4];typetest2=QuickSort;//[0,1,2,3,4,5,6,7,8,9]typeARR3=[1,1,0,1,1,0,0];typetest3=QuickSort;//[0,0,0,1,1,1,1]似乎一切正常。测试负数的时候可以发现负数少了。出现问题是因为初始size值比较是从0开始的，无限递归的结束条件是命中其中一个数，但是负数是永远不会命中的，这是一个致命的bug！优化：负数和负数的判断负数的特点：多一个符号，即“-”?转换为字符串后，取第一个字符判断是否为“-”?获取第一个字符类型为FuShu=`${T}`extends`${inferP}${string}`?Pextends'-':true:false;typei1=isFuShu<6>;//假类型i2=isFuShu<-6>;//truestringtonumber但是这样得到的是字符串，字符串转数字的逻辑和大小比较是一样的?无限递归，每次递归传入一个新的tuple?tuplelength(templateString)等于参数后结束递归，返回元组长度类型ToNumber=Sextends`${R['length']}`?R['长度']:ToNumber;如果判断值为负数，则需要获取负数的值?与判断负数的符号类似，获取加号后的字符串?通过泛型ToNumber类型将字符串转为数字GetFushu=`${T}`extends`${string}${inferU}`?ToNumber:0;完美获取绝对值?非负数返回自身，负数通过通用GetFushu类型获取GetAbs=isFuShuextendstrue?GetFushu:T;重构数的大小比较与负数和正数相反，正数必须大于负数。确定比较值是负数还是非负数。非负数由通用CompareV2进行比较。负数获取绝对值后，使用泛型CompareV2反转比较大小?非负数必须大于负数?泛型SmallerThan实现非负数比较，泛型SmallerThanV2实现负数和非负数的比较?GenericLargerThan和genericLargerThanV2类似于类型CompareV2={['SmallerThan']:T['length']延伸A？真：T['length']扩展了B？false:CompareV2,GetAbs,[...T,0]>['SmallerThan'];['SmallerThanV2']:isFuShuextendstrue?(isFuShuextendstrue?CompareV2['LargerThan']:true):(isFuShuextendstrue?false:CompareV2['SmallerThan']);['LargerThan']:T['length']扩展A？false:T['length']扩展B?真：CompareV2,GetAbs,[...T,0]>['LargerThan'];['LargerThanV2']:isFuShuextendstrue?(isFuShuextendstrue?CompareV2['SmallerThan']:false):(isFuShuextendstrue?true:CompareV2['LargerThan']);}测试用例typeh1=CompareV2<-8,-6>['SmallerThanV2'];//truetypeh2=CompareV2<8,-6>['SmallerThanV2'];//falsetypeh3=CompareV2<6,8>['SmallerThanV2'];//truetypeh4=CompareV2<-8,6>['SmallerThanV2'];//truetypei1=CompareV2<-8,-6>['LargerThanV2'];//falsetypei2=CompareV2<8,-6>['LargerThanV2'];//truetypei3=CompareV2<6,8>['LargerThanV2'];//falsetypei4=CompareV2<-8,6>['LargerThanV2'];//false重组快排重组泛型FilterV2（更换Compare->CompareV2）typeFilterV2,Zextendsnumber[]=[],Rextendsnumber[]=[],>=T['length']extendsR['length']?Z:FilterV2[key]extendstrue?[...Z,T[R['length']]]:Z,[...R,0]>;//快排类型QuickSortV2,T[0],'SmallerThanV2'>>,Largerextendsnumber[]=IsArray,T[0],'LargerThanV2'>>>=T['length']延伸0|1？吨：[...QuickSortV2,T[0],...QuickSortV2];测试快排V2typeARR4=[-5,-2,-4,-1,0,-6];typetest4=QuickSortV2;//[-6,-5,-4,-2,-1,0]typeARR5=[-5,-2,4,-1,0,-6,2,-3,7];typetest5=QuickSortV2;//[-6,-5,-3,-2,-1,0,2,4,7]typeARR6=[3,-2,7,-1,0,-6,9,-5,8,-4];typetest6=QuickSortV2;//[-6,-5,-4,-2,-1,0,3,7,8,9]