我试图了解在基数排序中使用不稳定排序算法(如快速排序)的危险。 另外,在这两种情况下(即 MSD 基数排序和 LSD 基数排序)都必须有稳定的算法吗?
提前致谢。
最佳答案
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
关于algorithm - 基数排序只使用稳定排序算法有什么必要?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/38627449/