使用Quick-Sort排序数位的修改版Radix Sort是否有效？求复杂度分析

一、算法有效性分析 #

你的朋友和你的观点都有部分道理，核心取决于修改的是哪种基数排序（LSD/低位优先 还是 MSD/高位优先）：

• 若修改的是LSD基数排序：算法无效，你朋友的观点正确。
  LSD基数排序的核心逻辑是从低位到高位依次排序，每一步必须依赖稳定排序——保证当按高位排序时，相同高位的元素能保留之前低位排序的相对顺序。快排是不稳定排序，会打乱相同高位元素的低位有序性，最终导致整体排序错误。比如数组[12,13,11]，LSD先按个位快排可能得到[11,13,12]，再按十位排序时，因所有元素十位相同，快排不会调整顺序，最终数组[11,13,12]是错误的。
• 若修改的是MSD基数排序：算法有效，你的观点正确（确实无实用价值）。
  MSD基数排序是从高位到低位依次排序，先按最高位将数组分成若干高位相同的分组，再对每个分组按次高位排序，以此类推。即使使用不稳定的快排，每个分组内的排序仅关注当前数位，所有数位处理完成后，元素的整体大小必然是有序的。即使不分组，直接对整个数组按当前数位排序，最后一轮处理最低位时，也会将相同高位的元素按低位排序，最终结果正确。

二、时间复杂度分析 #

你的最佳时间复杂度观点错误，正确的最佳时间复杂度应为O(d·n log n)：

• 快排的最佳时间复杂度是O(n log n)（当每次分区都能均分数组时）。
• 基数排序需要处理d个数位，每一轮都要对n个元素执行一次快排，因此总时间复杂度为d乘以单轮快排的时间，即O(d·n log n)。
• 你提到的log_d n不符合排序算法的下界（排序n个元素的时间复杂度不可能低于O(n)），显然是混淆了基数排序的基数参数和时间复杂度的关系。

内容的提问来源于stack exchange，提问作者liatkatz