基数排序, 此條目可参照外語維基百科相應條目来扩充, 若您熟悉来源语言和主题, 请协助参考外语维基百科扩充条目, 请勿直接提交机械翻译, 也不要翻译不可靠, 低品质内容, 依版权协议, 译文需在编辑摘要注明来源, 或于讨论页顶部标记, href, template, translated, page, html, title, template, translated, page, translated, page, 标签, 英語, radix, sort, 是一种非比较型整数排序算法, 其原理是将整数按位数切割成. 此條目可参照外語維基百科相應條目来扩充 若您熟悉来源语言和主题 请协助参考外语维基百科扩充条目 请勿直接提交机械翻译 也不要翻译不可靠 低品质内容 依版权协议 译文需在编辑摘要注明来源 或于讨论页顶部标记 a href Template Translated page html title Template Translated page Translated page a 标签 基数排序 英語 Radix sort 是一种非比较型整数排序算法 其原理是将整数按位数切割成不同的数字 然后按每个位数分别比较 由于整数也可以表达字符串 比如名字或日期 和特定格式的浮点数 所以基数排序也不是只能使用于整数 基数排序的发明可以追溯到1887年赫尔曼 何乐礼在列表機 Tabulation Machine 上的贡献 1 基数排序概况類別排序算法資料結構数组复杂度最坏时间复杂度O k N displaystyle O kN 空間複雜度O k N displaystyle O k N 最佳解Yes相关变量的定义它是这样实现的 将所有待比较数值 正整数 统一为同样的数位长度 数位较短的数前面补零 然后 从最低位开始 依次进行一次排序 这样从最低位排序一直到最高位排序完成以后 数列就变成一个有序序列 基数排序的方式可以采用LSD Least significant digital 或MSD Most significant digital LSD的排序方式由键值的最右边开始 而MSD则相反 由键值的最左边开始 效率 编辑基数排序的时间复杂度是O k n displaystyle O k cdot n 其中n displaystyle n 是排序元素个数 k displaystyle k 是数字位数 注意这不是说这个时间复杂度一定优于O n log n displaystyle O left n cdot log left n right right k displaystyle k 的大小取决于数字位的选择 比如比特位数 和待排序数据所属数据类型的全集的大小 k displaystyle k 决定了进行多少轮处理 而n displaystyle n 是每轮处理的操作数目 以排序n displaystyle n 个不同整数来举例 假定这些整数以B displaystyle B 为底 这样每位数都有B displaystyle B 个不同的数字 k log B N displaystyle k log B N N displaystyle N 是待排序数据类型全集的势 虽然有B displaystyle B 个不同的数字 需要B displaystyle B 个不同的桶 但在每一轮处理中 判断每个待排序数据项只需要一次计算确定对应数位的值 因此在每一轮处理的时候都需要平均n displaystyle n 次操作来把整数放到合适的桶中去 所以就有 k log B N displaystyle k approx log B N 所以 基数排序的平均时间T displaystyle T 就是 T log B N n displaystyle T approx log B left N right cdot n 其中前一项是一个与输入数据无关的常数 当然该项不一定小于log n displaystyle log n 如果考虑和比较排序进行对照 基数排序的形式复杂度虽然不一定更小 但由于不进行比较 因此其基本操作的代价较小 而且在适当选择的B displaystyle B 之下 k displaystyle k 一般不大于log n displaystyle log n 所以基数排序一般要快过基于比较的排序 比如快速排序 参考文献 编辑 US 395781 和UK 327 外部連結 编辑維基教科書中的相關電子教程 算法实现 排序 基数排序 取自 https zh wikipedia org w index php title 基数排序 amp oldid 75247241, 维基百科,wiki,书籍,书籍,图书馆,