快速排序vs Radix排序

Question

在编码考试中，我曾经问过这个问题：

假设您只按升序排序整数，您希望在最优先顺序速度时使用哪种算法，但您也希望节省空间？

选项是：

• LSD Radix排序
• 合并排序
• 快速排序

我认为可以在 LSD RADIX排序和 Quicksort 之间进行参数。

基数将在 $ o（kn）$ 和 Quicksort 中函数在 $ O（n \ log n）$ 和最坏情况， $ o（n ^ 2）$

我选择了 radix sort 作为答案，但我很奇怪别人不得不说的话。

Answer 1

这取决于...如果输入数字的数量是 $ n $ ，则假设字RAM计算模型， $ \ theta（\ log n）$ 比特，以及最坏的情况输入：

• Radix排序将需要 $ o（n \ log n）$ 时间和 $ o（n） $ 辅助空间。

• 具有固定或随机枢轴选择的Quicksort将需要 $ o（n ^ 2）$ 最坏情况时间和 $ O（\ log n）$ 辅助空间。

• mergeort需要 $ o（n \ log n）$ 时间和 $ o（n）$ < / span>辅助空间。

Radix排序和合并排序在此设置中等同。

请注意，使用随机PIVoIT选择的Quicksort导致 $ O（n \ log n）$ 的时间复杂度，具有很高的概率。确定枢轴以确定元素分为两个组的方式，其基数最多是恒定因子分开，除了<跨度类=“数学容器”> $ O（n \ log的算法n）$ 和 $ o（\ log n）$ 辅助空间。