排序算法，将在 O(n) 时间内对 n 个不同的整数进行排序

Question

有没有一种排序算法可以在 O(n) 时间内对从 3 到 4n 的 n 个不同整数进行排序？

我已经尝试这个问题一个小时了，但我不知道该怎么做。

有什么建议吗？

Answer 1

首先，基于比较的排序算法不能比最坏情况下的时间复杂度 O(nlogn) 更好，因此不要使用它们中的任何一个。

由于这是作业，请查看：

1. 计数排序
2. 桶排序
3. 基数排序

希望这会有所帮助。

Answer 2

是的，与大多数优化一样，您可以用空间换取时间，如以下伪代码所示：

def sortNums (nums[]):
    # Create 'isThere' array indicating if you're found the number.

    var isThere[3..(4*nums.count)] of boolean
    for i in 3..(4*nums.count):
        isThere[i] = false

    # Process each number in list, setting relevant 'isThere' entry to true.

    for each num in nums:
        isThere[num] = true

    # Process 'isThere' array to repopulate the number array in sorted fashion.
    pos = 0
    for i in 3..(4*nums.count):
        if isThere[i]:
            nums[pos] = i
            pos = pos + 1

它的工作原理如下：

1. 它创建一个布尔数组来指示是否已找到某个数字，最初将所有条目设置为 false 。这是一个 O(n) 操作，因为该数组的限制是 3 到 4n。您可以不用使用布尔值，因为数字是不同的。

2. 然后，对于列表中的每个数字，它将相关的布尔值设置为 true 以表明它在列表中 - 这又是 O(n)，因为您正在处理 n 个条目。< /p>

3. 然后，它按顺序重新填充数组，O(n)，原因与上述点 (1) 相同。

当然，它需要 O(n) 空间，而其他一些类型可能能够就地运行，但是，因为您没有对此进行限制（并且您的问题已明确将范围限制在可行的范围< support>(a))，我认为没问题。

---

^(a)如果没有限制范围，它很可能无法工作，仅仅是因为所需的空间可能很大。

Answer 3

我创建了一个称为“移位排序”的算法，在给定一些约束的情况下，该算法的运行时间复杂度为 O(n)。 可以在 http://sumofchoices.com/projects/sort.php 找到它

如果您愿意， 更传统的算法，使用桶、基数或计数算法。

Answer 4

由于您的范围是 [3, 4*N]，您可以将所有数字记录在二维数组 aux[N][4] 中 - 低两位数字的（即提醒模 4）确定列，高位（整数部分）确定行。

因此，您要做的第一件事是将辅助数组清零，然后对原始数组进行一次传递，将每个数字存储在 aux[a[i] div 4][a[i] mod 4] 中。

接下来考虑两个数字a和b，a a a。 b.。有两种情况：

1) a div 4 == b div 4；因此 a mod 4 a mod 4 b mod 4 因此，数字将位于 aux 中的同一行，但 a 将位于编号较低的列中。

2) a div 4 <; b div 4;因此，a 将位于编号较低的行中。

因此，按行主序遍历辅助数组并采用非零值将得到一个排序序列。

#include <stdio.h>
#include <string.h>

#define N 16 /* Range 3 - 4*N */

int a [] = { 5, 8, 11, 27, 18, 33, 3, 7, 10, 22, 64 };

#define M (sizeof a / sizeof a[0])

int aux[N][4];

void
sort  ()
{
  int i, j;

  memset (aux, 0, sizeof aux);

  for (i = 0; i < M; ++i)
    aux [a [i] >> 2][a [i] & 3] = a [i];

  j = 0;
  for (i = 0; i < N; ++i)
    {
      if (aux [i][0])
        a [j++] = aux [i][0];
      if (aux [i][1])
        a [j++] = aux [i][1];
      if (aux [i][2])
        a [j++] = aux [i][2];
      if (aux [i][3])
        a [j++] = aux [i][3];
    }
}


int
main ()
{
  int i;

  sort();
  for (i = 0; i < M; ++i)
    printf ("%d ", a [i]);
  puts ("");
  return 0;
}

编辑：但我更喜欢 paxdiablo 的解决方案

Answer 5

但是是否可以给定一个 log n 位整数 的数组 a[1....n]，并在 O(n)< 中对它们进行排序/代码> 时间。

Answer 6

http://www.cs.rutgers.edu/~muthu/soradix.pdf

基本上，该过程是桶排序，其中列表的辅助数据
实现了与每个桶相关联（即列表中元素之间的链接）
通过 P 中的伪指针而不是显式地将其存储在位存储器中
（缺乏字级并行性，访问效率低）。值得
注意到用伪指针实现的存储桶列表分布在
一个比我们通过显式指针获得的区域更大的区域（即
是因为每个伪指针都有一个 log n 位的键，而显式指针
将只有 log d 位）。

Answer 7

线性化珠排序在 O(kN) 时间和 O(2N) 空间中运行，其中 k 是要排序的最大值。

void sort(int A[], int N) {
    int i,count;
    int *R = calloc(N,sizeof(int));
    do {
       count=0;
       for (i=0;i<N;i++) { if (A[i]) { count++;  A[i]--;} }
       for (i=0;i<count;i++) { R[i]++; }
    } while(count);
    memcpy(A,R,N*sizeof(int));  //A is now sorted descending.
    free(R);
 }

请参阅这个 O(N*k) 排序算法是什么？

Answer 8

线程排序！

在单独的线程中发送数组的每个项目，告诉线程休眠等于整数值的平方的毫秒数，当线程唤醒时，它们会将其项目添加到数组中。