logo标签列表

如何在O(n)时间复杂度内对给定范围的列表进行排序

algorithmsorting
5
如果我有一个大小为n的列表，并且我知道列表中的数字将在1到2n之间，那么如果最坏情况为O(n)，我该如何解决它？
我想，如果它在1到n之间，我可以把数字取出来并将其与数组中该数字-1的值交换，但是如果存在任何重复项，则无法进行排序。
对于列表中的数字在1到2n之间的情况，我考虑了类似的方法，但是我无法弄清楚。请帮帮我？
n可以有多大？只要n不比列表的长度大太多，计数排序是迄今为止最快的解决方案。 - Tesseract
不是非常关于Java的问题... - RichardPlunkett
@SpiderPig n 将是列表的大小，其中 n 可以是任意大小。 - capa_matrix
4个回答
7
计数排序 可以在您的情况下以 O(n) 运行。请查看维基百科的定义。

计数排序是一种用于按键排序的算法，这些键是小整数；也就是说，它是一种整数排序算法。它通过计算具有每个不同键值的对象数量，并使用这些计数上的算术来确定输出序列中每个键值的位置来操作。它的运行时间与项数和最大键值与最小键值之间的差异成线性关系，因此仅适用于键的变化不显著大于项数的直接使用情况。

http://en.wikipedia.org/wiki/Counting_sort

5

如果你已经掌握某些信息，通常需要使用非比较排序算法才能在O(n)时间内进行排序。有三种“主要”的非比较排序算法可供选择：计数排序、基数排序和桶排序。

如果你知道输入是小整数，可以使用计数排序。据维基百科，“计数排序仅适用于关键字的变化不显著大于项数的情况。”http://en.wikipedia.org/wiki/Counting_sort

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

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

0
你可以使用基数排序，计数排序，有许多O(n)的排序算法。
但问题确实非常简单...
在Java中：
int [n] input = {your list of n numbers}; int [2*n] listinorder; int [n] output;

for (int i=0, i<2n, i++) listinorder[i] = -1; // set all values of listinorder to -1

for (int i=0, i < n, i++) listinorder[input[i]] = input[i]; // set the ith value of listinorder to i

int j=0;

for (int i=0, i<2n, i++) if (listinorder(i)  != -1) {output[j] = i; j++};

In Chinese:

  1. 建立长度为2n的数组（例如listinorder）。
  2. 将每个值设为-1。遍历输入列表。
  3. 对于输入列表中的每个值i，将相应的listinorder值设置为i（即listinorder [i] = i）。然后遍历不是-1的listinorder值以生成排序列表。

所有步骤都是O（n）。

"listinorder[i]=i" - 你假设输入中任何给定的数字都只出现一次。 - Tony Delroy
0
1
计数比基数排序更适合解决这种明确定义的问题。 - RichardPlunkett
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接