刷题
刷题
learn
learn
日期
Aug 31, 2024
- 基于比较的排序：只需要定义好两个对象之间怎么比较即可，对象的数据特征并不关心，很通用
- 不基于比较的排序（基数排序、计数排序、桶排序）：和比较无关的排序，对于对象的数据特征有要求，并不通用
计数排序，非常简单，但是数值范围比较大了就不行了
基数排序的实现细节，非常优雅的一个实现
关键点：前缀数量分区的技巧、数字提取某一位的技巧
时间复杂度，额外空间复杂度，需要辅助空间做类似桶的作用，来不停的装入、弹出数字
- 一般来讲，计数排序要求，样本是整数，且范围比较窄；
- 一般来讲，基数排序要求，样本是10进制的非负整数
如果不是就需要转化，代码里做了转化，并且代码里可以设置任何进制来进行排序
一旦比较的对象不再是常规数字，那么改写代价的增加是显而易见的，所以不基于比较的排序并不通用
- 如果有一个数字
num，如何提取出其每一位数字？
- 设置一个变量
offset = 1，每次都乘10；
- 每一位上的数字都可以这么得到：
(num / offset) % 10