在O(n)运行时间内对数组进行排序

Question

如果在内存方面没有任何限制，是否有一种算法可以在O(n)的时间复杂度下对给定含有重复元素的数组进行排序？

- RagHaven

---

http://en.wikipedia.org/wiki/Sorting_algorithm - lc.

意思是什么意思？虽然它需要一个非平凡的计算设备。 - Switzy

Answer 1

这取决于情况。如果您可以通过上下限（以及最大精度/值长度）对输入进行某种方式的绑定，那么您可以使用基数排序(Radix Sort)，其时间复杂度为O(n)。同样地，桶排序(Bucket Sort)在最佳情况下可以达到O(n)的复杂度，但在糟糕的输入情况下会退化为O(n^2)。

然而，通常情况下，如果您无法对输入进行约束并需要使用基于比较的排序，则可以证明O(n log n)是最优解。

当对定长整数或浮点数（通常高达64位）进行排序时，这些值实际上已被限制，因此可以使用基数排序。

即使值的最大位长受到限制，位长越长，常数就越大。实际上，如果要对n个值进行排序，并且每个值的长度或精度最多可达到m位，算法的复杂度为O(nm)。

- Yuushi

---

是的，你如何用 n 的术语来表达 m 呢？嗯，m 是 O(log n)，对吧？所以毕竟你不能比 O(n log n) 更好了。 - ThomasMcLeod

m不一定是以n为单位的。我可能有100万个8位整数要排序。这只意味着存在重复。 - ronalchn

Answer 2

是的。如果您对空间复杂度没有限制，那么可以使用o（n）时间复杂度对数组进行排序。

• 假设您有一个包含k（假设k = 10）个元素的数组。

• 并且（假设）您的数组为：N [2、6、4、4、1、1、9、5、2、2]

• 现在，根据我们的考虑，我们对空间没有任何限制。

• 假设我们有一个二维数组（temp_number [i] [j]），其大小为p（理论上，考虑p为无限大），其中索引i包含一些标志，而索引j包含一个链接列表。

现在，填充temp_number [][]，使数组N的每个元素都放在temp_number [][]的索引中，并使flag = 1，否则保持flag = 0。

temp_number[0][1] = [1][1->1->null]
 temp_number[1][1] = [1][2->2->2->null]
 temp_number[2][1] = [0][3->null]
 temp_number[3][1] = [1][4->4->null]
 temp_number[4][1] = [1][5->null]
temp_number[5][1] = [1][6->null]
temp_number[6][1] = [0][null]
temp_number[7][1] = [0][null]
temp_number[8][1] = [1][9->null] & so on...

现在，你可以在一个循环中获取所有具有flag=1的元素。

请注意，在这种方式中，我们不像这样进行操作：

if(number1 > number2) { //sorting logic... }

因此，您可以获得复杂度0(n)，因为只有一个循环。

- Manan Shah