使用typescript類型來實(shí)現(xiàn)快排詳情
更新時(shí)間：2022年08月14日 09:41:44 作者：東東么么噠
這篇文章主要介紹了使用typescript類型來實(shí)現(xiàn)快排詳情，文章圍繞主題展開詳細(xì)的內(nèi)容介紹，具有一定的參考價(jià)值，需要的小伙伴可以參考一下
前言
本文執(zhí)行環(huán)境typescript，版本4.7.4
不使用typescript的計(jì)算能力，通過類型來實(shí)現(xiàn)快排
元組快排
能否將元組 [3, 1, 2, 4] 通過泛型轉(zhuǎn)換成 [1, 2, 3, 4]
如何實(shí)現(xiàn)快排？
- 遍歷元組
- 元組每個(gè)值的大小比較
- 每次比較中挑選出符合條件的值，也就是實(shí)現(xiàn) Filter
實(shí)現(xiàn)邏輯
實(shí)現(xiàn)數(shù)字的大小比較
在typescript類型中沒有比較符，那如何判斷 5 和 6 誰更大？
typescript類型不知道，所以需要找到在typescript中已經(jīng)存在的遞增數(shù)列，通過這個(gè)數(shù)列來實(shí)現(xiàn)
怎么理解呢？
類似有 張三 和 李四 兩個(gè)人，要比較他們誰的位置靠前，需要有一個(gè)他們排隊(duì)的數(shù)列，然后依次查看，先看到 張三，那么 張三 的位置明顯靠前
typescript中有這樣的遞增數(shù)列嗎？
有的：元組下標(biāo)，只需要遞歸元組，就可以實(shí)現(xiàn)依次點(diǎn)名
實(shí)現(xiàn) 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]>;實(shí)現(xiàn) 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]>;當(dāng)然也可以依賴 SmallerThan 泛型來實(shí)現(xiàn)
type LargerThan<
A extends number,
B extends number,
T extends number[] = []
> = SmallerThan<A, B, T> extends true ? false : true;實(shí)現(xiàn)Filter
- 根據(jù)元組長度遞歸
- 當(dāng)滿足條件（比如：大于等于 一個(gè)值），將值存儲到新元組中，否則不操作
- 依賴上面實(shí)現(xiàn)的大小值比較 分別實(shí)現(xiàn) 對應(yīng)的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]
>;優(yōu)化Filter
Filter寫的很重復(fù)了，將泛型作為參數(shù)傳進(jìn)去
重構(gòu)數(shù)字的大小值比較
如何把泛型作為參數(shù)傳入，然后在參數(shù)中限定...好問題
// 目標(biāo)是實(shí)現(xiàn)這種 type Test<A extends number, T extends ?> = T<A>;
貌似不太行，那變個(gè)思路：
實(shí)現(xiàn)一個(gè)對象，每個(gè)鍵值對實(shí)現(xiàn)一個(gè)泛型，最后只需要傳入這個(gè)對象的key來獲取泛型，在參數(shù)的限定可以變成對key的限定，通過keyof 對象即可實(shí)現(xiàn)
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'>;復(fù)用邏輯，將對應(yīng)的泛型改成鍵值對
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'];
}重構(gòu)Filter
復(fù)用邏輯，將對應(yīng)的泛型改成鍵值對，key需要手動(dòng)傳入
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]
>;實(shí)現(xiàn)快排
- 遞歸元組
- 元組長度小于等于1的時(shí)候返回自身
- 默認(rèn)取第一項(xiàng)作為對比值
- 遞歸的參數(shù)通過filter和第一項(xiàng)比較
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]
看起來一切正常，可以發(fā)現(xiàn)遺漏了負(fù)數(shù)
測試負(fù)數(shù)的時(shí)候問題出現(xiàn)了
因?yàn)樽铋_始的大小值對比，是從0開始無限遞歸的
結(jié)束條件是命中其中一個(gè)數(shù)，然而負(fù)數(shù)是永遠(yuǎn)不會命中，這就是致命bug！
優(yōu)化：負(fù)數(shù)
負(fù)數(shù)的判斷
負(fù)數(shù)的特點(diǎn)：多了一個(gè)符號，也就是 '-'，轉(zhuǎn)換成字符串后拿第一個(gè)字符判斷
type isFuShu<T extends number> = `${T}` extends `${infer P}${string}` ?
P extends '-' : true : false;
type i1 = isFuShu<6>; // false
type i2 = isFuShu<-6>; // true字符串轉(zhuǎn)數(shù)字
但是這樣拿到的是字符串，還要把字符串轉(zhuǎn)成數(shù)字
和大小比較的邏輯一樣
- 無限遞歸，每次循環(huán)創(chuàng)建新元組
- 元組長度（模板字符串） 等于 參數(shù)后結(jié)束遞歸，并返回元組長度
type ToNumber<S extends string, R extends number[] = []> =
S extends `${R['length']}` ?
R['length'] : ToNumber<S, [...R, 0]>;獲取負(fù)數(shù)的值
判斷是負(fù)數(shù)后要拿到負(fù)數(shù)的值
- 和負(fù)數(shù)符號判斷類似，獲取除開符號之后的字符串，轉(zhuǎn)數(shù)字
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;
重構(gòu)數(shù)字的大小比較
負(fù)數(shù)的對比和正數(shù)相反，且正數(shù)一定比負(fù)數(shù)大
- 非負(fù)數(shù)數(shù)直接比較
- 負(fù)數(shù)取反比較
- 非負(fù)數(shù)一定大于負(fù)數(shù)
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
重構(gòu)快排
- 更換重構(gòu)的泛型
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]
到此這篇關(guān)于使用typescript類型來實(shí)現(xiàn)快排詳情的文章就介紹到這了,更多相關(guān)typescript實(shí)現(xiàn)快排內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
uni-app實(shí)現(xiàn)熱更新的詳細(xì)操作步驟
隨著 App 成功上架,可能更新頻率往往會越來越高,傳統(tǒng)的應(yīng)用更新方式要求用戶重新下載并安裝應(yīng)用,這不僅耗費(fèi)用戶大量時(shí)間、流量,還嚴(yán)重影響用戶體驗(yàn),為了提升用戶體驗(yàn),熱更新技術(shù)應(yīng)運(yùn)而生,所以本文介紹了uni-app實(shí)現(xiàn)熱更新的詳細(xì)操作步驟,需要的朋友可以參考下2025-04-04
今天小編就為大家分享一篇layer彈出層擴(kuò)展主題的方法，具有很好的參考價(jià)值，希望對大家有所幫助。一起跟隨小編過來看看吧2019-09-09
JavaScript實(shí)現(xiàn)自動(dòng)跳轉(zhuǎn)文本功能
這篇文章主要為大家詳細(xì)介紹了JavaScript自動(dòng)跳轉(zhuǎn)文本功能，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2017-05-05
微信小程序開發(fā)之表單驗(yàn)證WxValidate使用
本文主要介紹了微信小程序開發(fā)之表單驗(yàn)證WxValidate使用，文中通過示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2021-10-10
JavaScript中數(shù)組flat方法的使用與實(shí)現(xiàn)方法
在Array的顯示原型下有一個(gè)flat方法,可以將多維數(shù)組,降維,傳的參數(shù)是多少就降多少維,下面這篇文章主要給大家介紹了關(guān)于JavaScript中數(shù)組flat方法的使用與實(shí)現(xiàn)的相關(guān)資料,需要的朋友可以參考下2022-08-08
本文主要介紹了JS調(diào)用Android、Ios通信的相同點(diǎn)和不同點(diǎn)，以便幫助我們在進(jìn)行混合式開發(fā)時(shí)，提高代碼質(zhì)量，實(shí)現(xiàn)兩者在網(wǎng)頁端代碼的統(tǒng)一。下面跟著小編一起來看下吧2017-01-01
原生JS實(shí)現(xiàn)圖片輪播 JS實(shí)現(xiàn)小廣告插件
這篇文章主要為大家詳細(xì)介紹了原生JS實(shí)現(xiàn)圖片輪播、小廣告插件，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2021-09-09
多種方法實(shí)現(xiàn)load加載完成后把圖片一次性顯示出來
如何一個(gè)load 加載完成后把圖片一次性顯示出來，下面有個(gè)不錯(cuò)的方法，希望對大家有所幫助2014-02-02
這篇文章主要介紹了觸屏中的JavaScript事件,實(shí)例分析了觸屏事件的種類、原理與相關(guān)使用技巧,需要的朋友可以參考下2015-02-02
這篇文章主要給大家介紹了d3.js中強(qiáng)制異步文件讀取同步的幾種方法，文中給出了詳細(xì)的介紹和解決方法，對大家具有一定的參考價(jià)值，需要的朋友們下面來一起學(xué)習(xí)學(xué)習(xí)吧。2017-02-02