问题描述
有人问我一个有趣的问题，在我的采访，在Atrenta公司。这是一个包含有一个O（n）的复杂性，我说的是不可能的排序，但他坚持说，即使在面试后。
I was asked an interesting question at my interview at Atrenta. It was to sort an array with an complexity of O(n) which I said is not possible but he insisted it is, even after the interview.
这是这样的。
您有一个数组，可以说：[1,0,1,0,1,1,0]，这需要进行排序。什么都必须在阵列内完成（在这个意义上没有其它数据结构涉及
You have an array, lets say : [1,0,1,0,1,1,0] and this needs to be sorted. What ever has to be done within the array (in the sense no other data structure involved.
我没有，我不认为这是可以做到任何形式用的O（n）的复杂性。我能想到的最好的为O（n * log n）的，我的知识来源于维基百科。
I haven't and I don't think it is possible to do any sort with an complexity of O(n). The best I could think of is O(n * log n) and my knowledge comes from Wikipedia.
请给我你的想法和很好的方式来做到这一点，如果你知道。
Please give me your ideas and well a way to do it if you know.
推荐答案
在你的例子中有数组中只有两种不同的价值观，所以你可以用计数排序：
In your example there are only two different values in the array, so you could use counting sort:
zero_count = 0
for value in array:
if value == 0:
zero_count += 1
for i in 0 ... zero_count:
array[i] = 0
for i in zero_count ... array.size:
array[i] = 1
板蓝根排序是一个家庭的更普遍适用的O（n）的排序。
Radix sorts are a family of more generally applicable O(n) sorts.
这是比较各种需要欧米茄的（N * log n）的平均值比较，因此不能运行在最坏情况或平均情况的线性时间。
It is comparison sorts that require Omega(n * log n) comparisons on average and hence cannot run in worst-case or average-case linear time.
这篇关于为O排序阵列（n）的复杂性的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！