algorithm - 基数排序只使用稳定排序算法有什么必要？

Question

我试图了解在基数排序中使用不稳定排序算法(如快速排序)的危险。另外，在这两种情况下(即 MSD 基数排序和 LSD 基数排序)都必须有稳定的算法吗？

提前致谢。

Answer 1

MSD 基数排序通常不实用，因为在每次通过后无法连接虚拟容器。如果按 8 位字节排序，在第一次通过后你有 256 个独立的 bins，两次通过后，65536 个 bins，三次通过后，16777216 个 bins，......。

更新 - 一个异常(exception)是只执行一次 MSD 传递以将大型阵列拆分为 256(或 512 或 1024 或...)个容器，目标是每个容器都适合缓存。这假设分布有些均匀，因此 bin 的大小相似。在初始 channel 之后，然后使用 LSD channel 对每个 bin 进行排序，这可以通过多个线程完成(如果是 4 个内核，则 LSD 使用 4 个线程一次对 4 个 bin 进行排序)，因为 bin 之间不会出现冲突问题。

LSD 基数排序需要稳定，因为虚拟容器是按顺序连接的，并且后续传递的更重要的“数字”需要保留先前传递建立的顺序。请注意，LSD 基数排序是可追溯到 1900 年代初期的旧卡片分类器的操作方式。

http://en.wikipedia.org/wiki/IBM_card_sorter#Earlier_sorters