我应该在这种情况下使用哪种排序算法？

Question

研究人员拥有1亿人的记录数据库.研究人员希望根据其他标准(如星座,出生年份等)研究给定名称的分布,因此希望按名称排序,以后再进行进一步排序.

我应该使用哪种？

A.选择
B.快速
C.堆
D.插入
E.合并

谢谢!

Answer 1

自从你亲自到达以来,这不是我的答案,但这里是为了更好的可见性:

1. 可以排除选择和插入,因为它们具有O(n^2)平均运行时间,对于100M项目不会削减它.
2. Heapsort和quicksort被排除在外,因为它们不稳定.此问题需要稳定排序,因为问题定义意味着在进一步排序时,需要维护原始顺序(按名称).
3. 这只会使mergesort成为合适的候选者.

更新:与考试相关的建议

我不得不承认上面的第2点(按名称保留排序)在问题描述中并不完全清楚.但是,这是一个考试问题,必须有一些方法可以将选项缩减为一个.这只能通过要求稳定的排序来实现,所以即使措辞不是铁定的,也要求有这样的要求.

这种实践思维方式使得恕我直言更容易获得某些类型的考试问题的明确答案.