如何（百万/十亿/ ...）整数排序？ [英] How to sort (million/billion/...) integers?

问题描述

有时候，面试官会问你如何排序百万/十亿的32位整数（如<一个href="http://www.glassdoor.com/Interview/Sort-a-million-32-bit-integers-using-only-2MB-of-RAM-QTN_120936.htm">here和<一href="http://www.glassdoor.com/Interview/How-would-you-sort-an-array-of-one-billions-integers-QTN_116071.htm">here).我猜他们希望应聘者比较O（N *日志（N））排序与基数排序。对于万元整数O（N *日志（N））的排序可能是更好的，但是对于十亿他们很可能是相同的。这会让有意义吗？

Sometimes interviewers ask how to sort million/billion 32-bit integers (e.g. here and here). I guess they expect the candidates to compare O(N*Log(N)) sort with radix sort. For million integers O(N*Log(N)) sort is probably better but for billion they are probably the same. Does it make sense ?

推荐答案

如果你得到像这样的问题，他们不是在寻找的答案。他们正在试图做的是看你如何思考的一个问题。你跳权，或者你询问有关项目的要求吗？

If you get a question like this, they are not looking for the answer. What they are trying to do is see how you think through a problem. Do you jump right in, or do you ask questions about the project requirements?

有一个问题你最好问的是，如何解最优确实这个问题需要？也许存储在一个文件中的冒泡排序的记录是不够好，但你要问。请教一下，如果输入变为64位的数字，应在排序过程中很容易地更新吗？问多久，程序员必须发展计划。

One question you had better ask is, "How optimal of solution does the problem require?" Maybe a bubble sort of records stored in a file is good enough, but you have to ask. Ask questions about what if the input changes to 64 bit numbers, should the sort process be easily updated? Ask how long does the programmer have to develop the program.

这些类型的问题，让我知道候选人是明智地看到，还有更多的问题不仅仅是排序数字。

Those types of questions show me that the candidate is wise enough to see there is more to the problem than just sorting numbers.

这篇关于如何（百万/十亿/ ...）整数排序？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！