如何使用最小写入数对数组进行排序？
如何使用最小写入数对数组进行排序？
提问于 2010-09-02 10:43:19
我的朋友在面试中被问到一个问题：
面试官给了他一组未排序的数字，并让他排序。限制是写入的数量应该最小化，而对读取的数量没有限制。
回答 2
Stack Overflow用户
发布于 2010-09-02 10:58:39
您可以使用非常简单的算法来满足您的需求。
算法应该如下所示：
i = 0
do
search for the minimum in range [i..n)
swap a[i] with a[minPos]
i = i + 1
repeat until i = n.搜索最小值几乎不需要任何成本，交换需要3次写入，i++需要1..
正如ash所说的那样，这被命名为selection sort。(对不起，我不知道这是选择排序:( )
Stack Overflow用户
发布于 2010-09-02 21:52:31
我在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
endfinalarray将拥有最终的排序数组，您将有o(N)个写操作，其中N是数组的范围。同样，当使用特定范围内的键时，这是很有用的，但这可能是您的情况。
致以最良好的问候，并祝你好运！
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/3623509
复制相关文章
相似问题