问如何使用最小写入数对数组进行排序？

EN

我在O(n)中所指的排序类似于选择排序(上一篇文章)，当你有一个很小的键范围(或者你在两个范围之间对数字进行排序)时很有用。

如果您有一个数字数组，其中的数字将介于-10和100之间，那么您可以创建一个包含110的数组，并确保所有数字都可以放入其中，如果您考虑重复的数字，则概念是相同的，但是您将在排序的数组中使用列表而不是数字

伪想法是这样的：

N: max value of your array
tosort //array to be sorted
sorted = int[N]

for i = 0 to length(tosort)
do
   sorted[tosort[i]]++;
end

finalarray = int[length(tosort)]

k = 0
for i = 0 to N
do
  if ( sorted[i] > 0 )
    finalarray[k] = i
    k++;
  endif
end

finalarray将拥有最终的排序数组，您将有o(N)个写操作，其中N是数组的范围。同样，当使用特定范围内的键时，这是很有用的，但这可能是您的情况。

致以最良好的问候，并祝你好运！