在线性时间内对 [log n] 不同值进行排序

Question

我有一个 n 个整数数组，它只能假设 log n 个可能值（和任何值）。例如S = [349,12,12,283,349,283,283,12]中，只有3个不同的数字(log 8 = 3).

我必须在不到 O(nlogn) 的时间内对这个数组进行排序。我应该使用哪种算法？也许基数排序与计数排序？它的分析呢？

Answer 1

基数排序的复杂度是 O(dn)，d 是数字中的位数。

算法运行仅当d为常量时线性时间为秒！在您的情况下 d = 3log(n) 并且您的算法将运行 in O(nlog(n)).

老实说，我不确定如何在线性时间内解决这个问题。是否还有关于数字性质的任何其他信息我想知道是否还缺少关于数字性质的任何其他信息...

好吧，这是 DNA 的 MSD 基数排序的简单实现。它是用 D 语言编写的，因为这是我使用最多的语言，因此最不可能犯愚蠢的错误，但它可以很容易地翻译成其他语言。它就地但需要 2 * seq.length 遍历数组。

void radixSort(string[] seqs, size_t base = 0) {
    if(seqs.length == 0)
        return;

    size_t TPos = seqs.length, APos = 0;
    size_t i = 0;
    while(i < TPos) {
        if(seqs[i][base] == 'A') {
             swap(seqs[i], seqs[APos++]);
             i++;
        }
        else if(seqs[i][base] == 'T') {
            swap(seqs[i], seqs[--TPos]);
        } else i++;
    }

    i = APos;
    size_t CPos = APos;
    while(i < TPos) {
        if(seqs[i][base] == 'C') {
            swap(seqs[i], seqs[CPos++]);
        }
        i++;
    }
    if(base < seqs[0].length - 1) {
        radixSort(seqs[0..APos], base + 1);
        radixSort(seqs[APos..CPos], base + 1);
        radixSort(seqs[CPos..TPos], base + 1);
        radixSort(seqs[TPos..seqs.length], base + 1);
   }
}

显然，这是 DNA 特有的，而不是一般的，但应该很快。

编辑：我很好奇这段代码是否真的有效，所以我在等待我自己的 生物信息学 代码到运行时 tested/debugged 它。上面的版本现在已经过实际测试并且可以工作。对于每个 5 个碱基的 1000 万个序列，它比优化的 introsort.

快大约 3 倍

让我们看一下带有两位十进制数的示例：

49, 25, 19, 27, 87, 67, 22, 90, 47, 91

按第一位数字排序

19, 25, 27, 22, 49, 47, 67, 87, 90, 91

接下来，您按第二位数字排序，得到

90, 91, 22, 25, 27, 47, 67, 87, 19, 49

好像不对吧？或者这不是你在做什么？如果我弄错了，也许你可以告诉我们代码。

如果您对具有相同第一位数字的所有组进行第二次桶排序，您的算法将等同于递归版本。也会很稳定。唯一的区别是您将按广度优先而不是深度优先对桶进行排序。

更新

检查这个答案：sort O(nlogn)

Answer 2

由于假定只有 log(n) 个唯一元素，您可以使用以下算法在 O(n) 时间内获得排序列表：

创建列表中有多少不同项的映射，并保留每个项的计数（基本上是 dictionary/hashmap 键，计数）
- 这是对输入列表的单次迭代，因此 O(n) 步。
根据键对上述大小为 log(n) 的元组列表进行排序。
- 假设我们使用归并排序，那么归并排序的时间复杂度是k*log(k)，其中k是输入的大小。
- 将 k 替换为 log(n)，我们得到此步骤的复杂度为 O(log(n)*log(log(n)))。
- 由于复杂度O(log(n)*log(log(n))) < O(n)，所以到这一步的整体复杂度为O(n) + O(log(n)*log(log(n)))，又等同于O(n)[=38] =]
迭代排序的键，并使用单个 for 循环生成排序的列表，其中每个值按其计数重复。这里最多 O(n) 次迭代。

总的来说，上面的算法将在 O(n) 时间内运行。

Answer 3

计算列表中每个元素的数量（使用哈希表）（时间：O(n)）。
删除重复列表（时间：O(n)）。
对现在去重的项目进行排序（时间：O(log n * log log n)）。
构建一个包含每个项目的正确副本数的列表（时间：O(n)）。

总的来说，这是 O(n) 并且易于实现。

这里有一些 python 实现了这个：

def duplicates_sort(xs):
    keys = collections.Counter(xs)
    result = []
    for k in sorted(keys):
        result.extend([k] * keys[k])
    return result

在线性时间内对 [log n] 不同值进行排序

Sorting [log n] different values in linear time

algorithm

sorting

radix-sort