基数排序

易经学习

天地变化的道理

分类目录

使用率很高网站

文章列表

生活要常常分享

维基百科

您身边百科全书

产品秀秀

免费为您秀产品

基数排序

基数排序基数排序（）是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。它是这样实现的：将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后，数列就变成一个有序序列。基数排序的方式可以采用LSD（Least significant digital）或MSD（Most significant digital），LSD的排序方式由键值的最右边开始，而MSD则相反，由键值的最左边开始。历史. 基数排序的发明可以追溯到1887年赫尔曼·何乐礼在上的贡献。基数排序演算法早在1923年被广泛运用在打孔卡的排序。效率. 基数排序的时间复杂度是formula_1，其中formula_2是排序元素个数，formula_3是数字位数。注意这不是说这个时间复杂度一定优于formula_4，formula_3的大小取决于数字位的选择（比如比特位数），和待排序数据所属数据类型的全集的大小；formula_3决定了进行多少轮处理，而formula_2是每轮处理的操作数目。以排序formula_2个不同整数来举例，假定这些整数以formula_9为底，这样每位数都有formula_9个不同的数字，formula_11，formula_12是待排序数据类型全集的势。虽然有formula_9个不同的数字，需要formula_9个不同的桶，但在每一轮处理中，判断每个待排序数据项只需要一次计算确定对应数位的值，因此在每一轮处理的时候都需要平均formula_2次操作来把整数放到合适的桶中去，所以就有： formula_16 所以，基数排序的平均时间formula_17就是： formula_18 其中前一项是一个与输入数据无关的常数，当然该项不一定小于formula_19。如果考虑和比较排序进行对照，基数排序的形式复杂度虽然不一定更小，但由于不进行比较，因此其基本操作的代价较小，而且在适当选择的formula_9之下，formula_3一般不大于formula_19，所以基数排序一般要快过基于比较的排序，比如快速排序。外部连结. -{H|zh-hans:重定向;zh-hant:重新导向;}--{H|zh-cn:字符;zh-tw:字元;}--{H|zh-hans:文件; zh-hant:档案;}--{H|zh-hans:快捷方式; zh-hant:捷径;}--{H|zh-hans:项目;zh-hant:专案;zh-tw:计划;zh-hk:计划;zh-mo:计划;}--{H|zh-cn:计算机; zh-sg:电脑; zh-tw:电脑;}-

西屯区

电子材料

铝

物理气相沉积

溅射

锦鲤

欧洲鲤

翁偶虹

任长霞

梅森素数

使徒信经

尼西亚信经