使用typescript类型来实现快排详情

目录
  • 前言
  • 元组快排
  • 实现逻辑
    • 实现数字的大小比较
    • 实现 A 是否 小于或等于 B
    • 实现 A 是否 大于或等于 B
  • 实现Filter
    • 优化Filter
    • 重构数字的大小值比较
    • 重构Filter
    • 实现快排
  • 测试快排
  • 优化:负数
    • 负数的判断
    • 字符串转数字
    • 获取负数的值
    • 完善获取绝对值
    • 重构数字的大小比较
    • 重构快排
  • 测试快排V2

前言

本文执行环境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]

到此这篇关于使用typescript类型来实现快排详情的文章就介绍到这了,更多相关typescript实现快排内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • 详解TypeScript使用及类型声明文件

    目录 简介 Script 与 Vue3 defineProps 与 Typescript defineEmits 与 Typescript ref 与 Typescript computed 与 Typescript 事件对象 与 Typescript 模板 Ref 与 Typescript 可选链操作符 非空断言-TS TypeScript类型声明文件 基本介绍 内置类型声明文件 第三方库类型声明文件 自定义类型声明文件 简介 声明文件是以.d.ts为后缀的文件,开发者在声明文件中编写类型声明

  • 直观详细的typescript隐式类型转换图文详解

    正文 1.unknown是所有类型的父类型,其他类型都可以赋值给 unknown let a: undefined = undefined; let b: null = null; let x2: unknown; x2 = a; //正确 x2 = b; //正确 2.never 是任何类型的子类型,可以赋给任何类型 let a: undefined = undefined; let b: null = null; function err(): never { // OK throw new

  • 使用TypeScript类型注解的方法

    目录 类型注解 类型推导 TS和JS共有的数据类型 TS独有的数据类型 any unknown void never tuple 函数参数和返回值 类型断言 非空类型断言 字面量 类型缩小 总结 类型注解 TypeScript提供了很多数据类型,通过类型对变量进行限制,称之为类型注解,使用类型注解后,就不能够随意变更变量的类型. 以下代码定义了一个字符串类型的变量,如果把它更改为数字类型时,代码编译阶段就会直接报错,提示 “Type ‘number’ is not assignable to t

  • TypeScript中的类型断言[as语法|<>语法]的使用

    Typescript中类型断言官方解释 要理解好类型断言,其实就深刻理解一句话:你会比TypeScript更了解某个值的详细信息 . 类型断言,断言 断言,顾名思义,我断定怎么怎么样,代入这句话里就是,我断定这个类型是什么.当然这是我们主观上的思维逻辑,程序并不认可,所以我们需要告诉程序:“相信我,我知道自己在干什么” . 这么干说,大家可能还是理解的不够透彻,我用两个函数举一个例子: /** * @param d 日期 * @param f 想要格式化的字符串 */ function date

  • typescript返回值类型和参数类型的具体使用

    目录 返回值类型 可缺省和可推断的返回值类型 Generator 函数的返回值 参数类型 可选参数和默认参数 剩余参数 返回值类型 在 JavaScript 中,我们知道一个函数可以没有显式 return,此时函数的返回值应该是 undefined: function fn() { // TODO } console.log(fn()); // => undefined 需要注意的是,在 TypeScript 中,如果我们显式声明函数的返回值类型为 undfined,将会得到如下所示的错误提醒.

  • 使用typescript类型来实现快排详情

    目录 前言 元组快排 实现逻辑 实现数字的大小比较 实现 A 是否 小于或等于 B 实现 A 是否 大于或等于 B 实现Filter 优化Filter 重构数字的大小值比较 重构Filter 实现快排 测试快排 优化:负数 负数的判断 字符串转数字 获取负数的值 完善获取绝对值 重构数字的大小比较 重构快排 测试快排V2 前言 本文执行环境typescript,版本4.7.4 不使用typescript的计算能力,通过类型来实现快排 元组快排 能否将元组 [3, 1, 2, 4] 通过泛型转换成

  • 使用typescript类型实现ThreeSum

    目录 前言 思路整理 实现TwoSum 实现减法 元祖中是否包含差值 递归元组 测试 实现ThreeSum 实现排序 实现ThreeSum 测试 前言 本文执行环境typescript,版本4.7.4 不使用typescript的计算能力,通过类型来实现ThreeSum 思路整理 实现ThreeSum之前我们先降低下难度,实现TwoSum,因为TwoSum可以作为ThreeSum的基础泛型 TwoSum需要准备什么呢? 递归元组,模拟for循环 减法,递归过程中求出差值 对每一项差值判断是否存在

  • C语言中关于库函数 qsort 快排的用法

    目录 前言 一.库函数(qsort)的含义 二.(qsort)函数的实现方式,话不多说,请看. 1. 第一个参数 2. 第二个参数 3. 第三个参数 4. 第四个参数 1). 函数的参数 2). 这第四个参数的重点 三.函数实现 四.总结 前言 我也只是一个奋斗的程序猿,仅以此篇文章,作为我学习的见证,可能我的文采不好,有时候讲的词不达意,但我尽力去做好我想做的这些事情,如果此篇文章能够给各位读者带来一定的认识,那自然是最好的.若文章中有鄙人讲错了的,欢迎评论区指点.谢谢!!! 一.库函数(qs

  • C语言中的结构体快排算法

    目录 C语言结构体快排算法 基于结构体数组的快速排序 C语言结构体快排算法 代码: #include<stdio.h> #include<string.h> #include<stdlib.h> struct Stu{ char name[100]; //名字 char xue[100]; //学号 int c; //成绩 }stu[10010]; int comp(const void* a,const void* b) { struct Stu *aa = (str

  • C++ 中快排的递归和非递归实现

    快排的递归 void quickSort1(int* root,int low,int high) { int pat=root[low]; if(low<high) { int i=low,j=high; while(i<j) { while(i<j&&root[j]>pat) j--; root[i]=root[j]; while(i<j&&root[i]<pat) i++; root[j]=root[i]; } root[i]=pa

  • Java经典快排思想以及快排的改进讲解

    一.经典快排思想 前提条件:给定一个无序数组arr 取这个数组最后一个数 num 作为标准,将前面部分的数分为两部分,使得<=num的部分在左边,>num的数在右边: 然后将最后一个数和>num部分的第一个数进行交换,就使得原本在数组最后位置的num找到了正确的位置,它的左边都是比它小的以及和它一样的数,右边都是比它大的数 回到1,进行递归或迭代,使得所有的数都找到正确的位 二.通过荷兰国旗问题改进快排 什么是荷兰国旗问题? 已知一个整形数组arr,和一个整数num,请把小于num的数放

  • TypeScript类型声明书写详解

    本文总结一下TypeScript类型声明的书写,很多时候写TypeScript不是问题,写类型就特别纠结,我总结下,我在使用TypeScript中遇到的问题.如果你遇到类型声明不会写的时候,多看看lodash的声明,因为lodash对数据进行各种变形操作,所以你能遇到的,都有参考示例. 基本类型 // 变量 const num: number = 1; const str: string = 'str'; const bool: boolean = true; const nulls: null

  • python快排算法详解

    快排是python经典算法之一. 1.下面讲解的是什么是快排和快排的图示. 2.快排是一种解决排序问题的运算方法. 3.快排的原理:在数组中任意选择一个数字作为基准,用数组的数据和基准数据进行比较,比基准数字打的数字的基准数字的右边,比基准数字小的数字在基准数字的左边, 第一次排序之后分为比基准数据大或比基准数据小两个部分,用刚开始的方法继续排序,直到每个排序分组中只有一个数据或没有数据为止. 4.下面以[ 7 91 23 1 6 3 79 2 ]数组为例子,进行快排运算. 5.选基准:选择数组

  • 为react组件库添加typescript类型提示的方法

    以我自己的组件react-better-countdown为例, 首先在package.json里面添加types: types/index.d.ts, , 然后文件目录上添加对应文件夹和文件, 最后是index.d.ts文件的编写,具体看代码: import * as React from 'react'; interface CountdownProps { count?: number; dayText?: string | React.ReactElement; hourText?: s

  • C语言实现各种排序算法实例代码(选择,冒泡,插入,归并,希尔,快排,堆排序,计数)

    目录 前言 选择排序 冒泡排序 插入排序 归并排序 希尔排序 快速排序 堆排序 计数排序 总结 前言 平时用惯了高级语言高级工具高级算法,难免对一些基础算法感到生疏.但最基础的排序算法中实则蕴含着相当丰富的优化思维,熟练运用可起到举一反三之功效. 选择排序 选择排序几乎是最无脑的一种排序算法,通过遍历一次数组,选出其中最大(小)的值放在新数组的第一位:再从数组中剩下的数里选出最大(小)的,放到第二位,依次类推. 算法步骤 设数组有n个元素,{ a 0 , a 1 , - , a n } 从数组第

随机推荐