如何对O（n）中给定范围的列表进行排序 [英] How to sort a list with given range in O(n)

问题描述

如果我有一个大小为n的列表，并且我知道列表中的数字将在1到2n之间，那么在最坏的情况是O（n）的情况下，我该如何解决呢？

If I have a list of size n and I know that the numbers in the list will be between 1 and 2n how would I go about solving it where the worst case would be O(n)?

我在想，如果它在1到n之间，我可以将数字取而代之以该数字的数组值-1，但是如果有的话就不会排序任何重复。

I was thinking that if it was between 1 and n I could just take the number and swap it with the value of the array at that number - 1 but then it wouldn't sort if there were any duplicate.

我在想类似的方法来处理列表中1到2n之间的数字，但我似乎无法弄清楚。请问有什么帮助吗？

I was thinking of a similar approach for the list having number between 1 and 2n but I can't seem to figure it out. Any help please?

推荐答案

您通常需要进行非比较排序，以O（n）时间排序，但这是如果您已经获得某些信息。有三种主要非比较排序算法可供选择：计数排序，基数排序和存储桶排序。

You would usually need a non-comparison sort to sort in O(n) time, but this is if you are already given certain information. There are three "main" non-comparison sort algorithms to choose from: counting sort, radix sort, and bucket sort.

如果您知道输入是小整数，请使用计数排序。通过维基百科，计数排序仅适用于键的变化不明显大于项数的情况。 http://en.wikipedia.org/wiki/Counting_sort

Use counting sort if you know that the input are small integers. By Wikipedia, "counting sort is only suitable to use in situations where the variation in keys is not significantly greater than the number of items." http://en.wikipedia.org/wiki/Counting_sort

如果要排序的所有数字都具有相同数量的整数，则可以使用基数排序。例如：211、311、122。

You can use radix sort if all the numbers you are sorting have the same number of integers. Ex: 211, 311, 122.

桶排序似乎是您的最佳选择。您的方法听起来不错，但您不需要从1到2n的数组，每个数字都有一个索引。在存储桶排序中，可以有一个1到20的数组，并且每个元素内都有一个类似链表的东西。因此，如果您将数字109放置为它可能对应于索引10。

Bucket sort may seem like the best option for you. Your approach sounds good, but you do not need an array from 1 to 2n with an index for each number. In bucket sort, you can have an array from 1 to 20, and have something like a linked list within each element. So if you were placing the number 109 it could correspond to the index 10.

这篇关于如何对O（n）中给定范围的列表进行排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！