知识卡片

普通读书笔记卡 · 5654.c.1.a.2.a.15 · 生成模型:未记录

低位基数排序依赖逐轮稳定

理解等级:中级

低位优先基数排序先按最低位稳定排序,再逐位向高位处理。高位相同的记录必须保留已按低位建立的顺序,否则前面工作会被破坏;它不是每轮只要按当前位排好就够。

本书[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乘

    参考来源

    - 位置:《算法精解:C语言描述》第12章《基数排序的描述》(spine1350;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1316.html;u218-ch12-016)。 - 结论依据:218全部说明、两轮数字例及原XHTML全部sup实读,220/02973逐位图已读,明确p的digit含义与稳定性作用。 - 原始内容:最低有效位到最高有效位进行比较,依次排序,从而得到有序数据集合。我们来看一个例子,用基数排序对十进制数据{15,12,49,16,36,40}进行排序。在对个位进行排序之后,其结果为{40,12,15,16,36,49},在对十位进行排序之后,其结果为{12,15,16,36,40,49}。 有一点 - 位置:《算法精解:C语言描述》第12章《基数排序的实现与分析》(spine1352;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1318.html;u220-ch12-016)。 - 结论依据: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]。 - 原始内容:每一位上应用计数排序来对数据集合排序。在以下介绍的实现方法中,data初始包含size个无序整型元素,并存放在单块连续的存储空间中。当rxsort返回时,data中的数据集完全有序。 如果我们理解计数排序的方法,那么基数排序也就非常简单了。单个循环控制正在进行排序的位置(见示例12-7)。从最低位开 - 位置:《算法精解:C语言描述》第12章《问与答》(spine1357;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1323.html;u225-ch12-016)。 - 结论依据:225固定80字符宽DNA字符串例可按分块digit处理,但需明确字母编码/稳定性/空间;不是调用int rxsort直接排序1000万字符串。 - 原始内容:DNA的信息。这种情况下应该选择哪种排序算法? 答:基数排序。基数排序的性能表现取决于基值的选择和空间的限制。然而,选择基数排序的一个重要考量因素是:数据集中的元素是固定大小的,而且能够分割为更小的整型变量。 问:假设有10 000个C数据结构,它们包含一个航空公司的航班时刻表,我们需要此时刻表进行 - 位置:《算法精解:C语言描述》第12章《问与答》(spine1357;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1323.html;u225-ch12-016)。 - 结论依据:225提问说直接调用ctsort与实际rxsort不符:02974–02975内联按digit计数并搬完整元素。直接对digit数组调ctsort会丢掉与原记录的对应,需扩展提键/搬运机制;此实现为具体整数位简化。 - 原始内容:略作修改,来简化这种过程。 问:假设有220个128位的元素要进行排序。如果使用快速排序效率如何?如果使用基值为216的基数排序效率如何?哪种方法效率更高?假设元素的个数是210而不是220,那么快速排序和基数排序的表现又会如何? 答:用快速排序需要O(nlg n)=220×20=2.10×107乘