知识卡片
低位基数排序依赖逐轮稳定
低位优先基数排序先按最低位稳定排序,再逐位向高位处理。高位相同的记录必须保留已按低位建立的顺序,否则前面工作会被破坏;它不是每轮只要按当前位排好就够。
本书[15,12,49,16,36,40]按个位变为[40,12,15,16,36,49],再按十位变为[12,15,16,36,40,49]。十位都为1时,12在15/16前,正是稳定性保留个位次序的结果。
位不只指二进制单个bit,而是所选基数下的一组数字。218原XHTML为2⁸及2¹⁶,不是28或216:64位值可分为四个16位digit。扩到字符串须定义各位置、长度与顺序编码,不能把本例int函数直接当通用字符串排序。
220及02974–02975每轮用(data[j]/pval)%k取digit,计数后作前缀和,从尾向前按digit末端位置放整个data[j],不能只搬digit丢掉其他位。02973由[302,253,611,901,529,102]先按个位成[611,901,302,102,253,529],再十位、百位,最终[102,253,302,529,611,901]。
225固定80字符宽DNA字符串例可按分块digit处理,但需明确字母编码/稳定性/空间;不是调用int rxsort直接排序1000万字符串。
225提问说直接调用ctsort与实际rxsort不符:02974–02975内联按digit计数并搬完整元素。直接对digit数组调ctsort会丢掉与原记录的对应,需扩展提键/搬运机制;此实现为具体整数位简化。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
- · 低位基数排序依赖逐轮稳定
- · 基数排序的实现与分析
- · 问与答
原书出处 · 3 处
- · 查看原书依据
最低有效位到最高有效位进行比较,依次排序,从而得到有序数据集合。我们来看一个例子,用基数排序对十进制数据{15,12,49,16,36,40}进行排序。在对个位进行排序之后,其结果为{40,12,15,16,36,49},在对十位进行排序之后,其结果为{12,15,16,36,40,49}。 有一点
- · 查看原书依据
每一位上应用计数排序来对数据集合排序。在以下介绍的实现方法中,data初始包含size个无序整型元素,并存放在单块连续的存储空间中。当rxsort返回时,data中的数据集完全有序。 如果我们理解计数排序的方法,那么基数排序也就非常简单了。单个循环控制正在进行排序的位置(见示例12-7)。从最低位开
- · 查看原书依据
略作修改,来简化这种过程。 问:假设有220个128位的元素要进行排序。如果使用快速排序效率如何?如果使用基值为216的基数排序效率如何?哪种方法效率更高?假设元素的个数是210而不是220,那么快速排序和基数排序的表现又会如何? 答:用快速排序需要O(nlg n)=220×20=2.10×107乘