哪个排序算法，我应该在这种情况下使用？ [英] Which sorting algorithm should I use in this scenario?
问题描述
一个研究者具有100万条记录的人的数据库。该研究人员希望研究根据其他标准，如星座，出生年份等赐名的分布，所以想通过姓名与后来进一步排序选项进行排序。
A researcher has a database of 100 million records of people. The researcher wants to study the distribution of given names according to other criteria such as zodiac sign, birth year, etc, so wants to sort by name with the option of further sorting later.
我应该使用哪种类型？
一个。选择
B.快速
C.堆
D.插入
E.合并
A. selection
B. quick
C. heap
D. insertion
E. merge
谢谢！
推荐答案
这不是真的我的答案，因为你自己达到了它，但在这里是为了更好的可见性：
It's not really my answer since you reached it yourself, but here it is for better visibility:
- 选择和插入可以排除，因为他们有
为O（n ^ 2）平均运行时间，这是不会削减它的100M项目。 - 堆排序和快速排序的排除，因为他们并不稳定。这个问题需要一个稳定的排序，因为问题定义意味着进一步排序时，原始顺序（按名称）需要被维持。
- 在此只留下归并为一个合适的人选。
- Selection and insertion can be ruled out because they have
O(n^2)average running time, which isn't going to cut it for 100M items. - Heapsort and quicksort are ruled out because they are not stable. This problem needs a stable sort because the problem definition implies that when sorting further, the original order (by name) needs to be maintained.
- This only leaves mergesort as a suitable candidate.
更新：考试相关的咨询
我不得不承认这一点2以上（preserve的按名称排序）不是的完全的距离问题说明清楚。然而，这是一个问题考试和必须有修整选项降至1的一些的方式。这只是成为可能，要求一个稳定的排序，所以要求有即使写法是不是铁定的。
I have to admit that point 2 above (preserve the sort by name) is not totally clear from the problem description. However, this is an exam question and there has to be some way of trimming the options down to one. This is only made possible by demanding a stable sort, so the requirement is there even if the wording is not ironclad.
这样的实践思维使得恕我直言，更容易达成明确的答案对于某些类型的考题。
This way of practical thinking makes it IMHO much easier to reach definitive answers for some types of exam questions.
这篇关于哪个排序算法，我应该在这种情况下使用？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
