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

Question

如果您对内存没有任何限制，是否有任何算法可以对 O(n) 中具有重复项的给定数组进行排序？

Answer 1

这取决于。如果您可以以某种方式将输入与下限和上限（以及最大精度/值长度）绑定，那么您可以使用基数排序，即O(n). 类似地，桶排序在最好的情况下可能具有O(n)复杂性，但会O(n^2)因输入错误而降级。

但是，一般而言，如果您无法限制输入并需要使用基于比较的排序，则可以证明这O(n log n)是最佳的。

在对固定精度整数或浮点数（通常最多 64 位）进行排序时，这些值是有效有界的，并且可以进行基数排序。

即使值的最大位长是有界的，位长越长，常数越大。实际上，如果有 n 个值要排序，并且每个值的长度或精度可达 m 位，则算法复杂度为 O(nm)。

Answer 2

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

• 假设您有一个由 k（让 k =10）个元素组成的数组。

• 并且（让）您的数组是： N[2,6,4,4,1,1,9,5,2,2]

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

• 假设我们有一个大小为 p 的二维数组 (temp_number[i][j])（理论上，认为 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的元素。

• 注意，这里这样，我们不是在做like

  if(number1 > number2) { //排序逻辑... }

  所以，在这里你可以得到复杂度 0(n)，因为那里只有一个循环。