知识卡片
基数排序从低位开始
最低位优先的基数排序先按低位、再依次按更高位排序,每一轮都必须稳定,才能在高位相同时保留低位形成的次序。
对 d 位键、每位 k 种值,若每轮稳定排序耗时 Θ(n+k),总时间为 Θ(d(n+k))。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第8章 线性时间排序 · 查看原书依据
In order for radix sort to work correctly, the digit sorts must be stable.
参考来源
- 位置:《算法导论(第4版)》第 8 章 8.3 节(`OEBPS/chapter008.xhtml`,文本字符 [15000, 19000);图 8.3/Art_P326)。
- 结论依据:原文给出从低位到高位逐轮稳定排序的伪代码,并在引理 8.3 汇总运行时间。
- 原始内容:In order for radix sort to work correctly, the digit sorts must be stable.