为O排序阵列（n）的复杂性 [英] Sorting Array in O(n) complexity

问题描述

有人问我一个有趣的问题，在我的采访，在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）的复杂性的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！