知识卡片

普通读书笔记卡 · 3616.a.1

基数排序从低位开始

理解等级:中级

最低位优先的基数排序先按低位、再依次按更高位排序,每一轮都必须稳定,才能在高位相同时保留低位形成的次序。

对 d 位键、每位 k 种值,若每轮稳定排序耗时 Θ(n+k),总时间为 Θ(d(n+k))。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

    - 位置:《算法导论(第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.