这是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的，而不是普遍的，但它应该很快。

编辑:

我很好奇这个代码是否真的有效，所以在等待我自己的生物信息学代码运行时，我对它进行了测试/调试。上面的版本现在已经经过测试并且可以工作。对于1000万个每个5个碱基的序列，它比优化的引入排序快大约3倍。

如果你的数据集如此之大，那么我认为基于磁盘的缓冲区方法是最好的:

sort(List<string> elements, int prefix)
if (elements.Count < THRESHOLD)
return InMemoryRadixSort(elements, prefix)
else
return DiskBackedRadixSort(elements, prefix)


DiskBackedRadixSort(elements, prefix)
DiskBackedBuffer<string>[] buckets
foreach (element in elements)
buckets[element.MSB(prefix)].Add(element);


List<string> ret
foreach (bucket in buckets)
ret.Add(sort(bucket, prefix + 1))


return ret

我也会尝试分组到更大数量的桶，例如，如果你的字符串是:

GATTACA

第一个MSB调用将返回GATT的桶(总共256个桶)，这样就可以减少基于磁盘的缓冲区的分支。这可能会提高性能，也可能不会，所以不妨尝试一下。

我从未见过就地基数排序，从基数排序的性质来看，只要临时数组适合内存，我怀疑它比就地排序快得多。

原因:

排序对输入数组进行线性读取，但所有写入几乎都是随机的。从特定的N开始，这可以归结为每次写入的缓存丢失。这种缓存缺失会减慢你的算法。它是否到位并不会改变这种效果。

我知道这不会直接回答你的问题，但如果排序是一个瓶颈，你可能想要看看附近的排序算法作为预处理步骤(软堆的维基页面可能会让你开始)。

这可以很好地提高缓存的局部性。课本上的错位基数排序会表现得更好。写入仍然几乎是随机的，但至少它们会聚集在相同的内存块周围，这样就增加了缓存命中率。

但我不知道这在实践中是否可行。

顺便说一句:如果你只处理DNA字符串:你可以将一个字符压缩成两个比特，并打包大量数据。这将把内存需求减少到原始表示的四倍。寻址变得更加复杂，但无论如何，CPU的ALU在所有缓存丢失期间都有大量的时间。

我要冒个险，建议你切换到heap/堆排序实现。这个建议伴随着一些假设:

1. 您可以控制数据的读取
2. 你可以做一些有意义的排序数据，只要你“开始”得到它排序。

堆/堆排序的美妙之处在于，您可以在读取数据时构建堆，并且可以在构建堆的那一刻开始获得结果。

让我们后退一步。如果您非常幸运，可以异步读取数据(也就是说，您可以发布某种类型的读请求，并在某些数据准备就绪时收到通知)，那么您可以在等待下一个数据块进入(甚至来自磁盘)时构建堆的一块。通常，这种方法可以将一半排序的成本隐藏在获取数据所花费的时间之后。

读取数据之后，第一个元素就已经可用了。这取决于您将数据发送到哪里，这可能很棒。如果你要把它发送给另一个异步阅读器，或者一些并行的“事件”模型，或者UI，你可以不断地发送数据块。

也就是说，如果您无法控制如何读取数据，并且它是同步读取的，并且在完全写入之前对排序的数据没有任何用处，那么请忽略所有这些。：(

参见维基百科的文章:

• 堆排序
• 二进制堆

首先，考虑问题的编码。去掉字符串，用二进制表示代替它们。使用第一个字节表示长度+编码。或者，在四字节边界上使用固定长度的表示。基数排序就简单多了。对于基数排序，最重要的是不要在内部循环的热点处进行异常处理。

好的，我想了一下4元的问题。你需要一个类似朱迪树的解决方案。下一个解决方案可以处理可变长度的字符串;对于固定长度，只要去掉长度位，这实际上让它更简单。

分配16个指针的块。指针中最不重要的部分可以被重用，因为你的块总是对齐的。您可能需要为它使用一个特殊的存储分配器(将大的存储分解为较小的块)。有许多不同类型的积木:

• 用可变长度字符串的7个长度位进行编码。当它们填满时，你用:
• 位置编码接下来的两个字符，你有16个指针指向下一个块，以:
• 字符串最后三个字符的位图编码。

对于每种类型的块，您需要在lsb中存储不同的信息。当你有可变长度的字符串时，你也需要存储字符串的结尾，最后一种块只能用于最长的字符串。随着结构的深入，长度为7的位应该被更少的位所取代。

这为您提供了一个合理快速和非常有效的内存存储排序字符串。它的行为有点像单词查找树。要让它工作，请确保构建足够的单元测试。您希望覆盖所有块转换。你只想从第二种积木开始。

为了获得更好的性能，您可能需要添加不同的块类型和更大的块大小。如果块总是相同的大小和足够大，您可以为指针使用更少的位。块大小为16个指针，在32位地址空间中已经有一个字节空闲。查看Judy树文档，了解有趣的块类型。基本上，您添加代码和工程时间以进行空间(和运行时)权衡

您可能希望从头四个字符的256宽直接基数开始。这提供了一个不错的空间/时间权衡。在这个实现中，你得到的内存开销比简单的trie少得多;它大约小了三倍(我还没有测量过)。如果常数足够低，O(n)不是问题，就像你在与O(n log n)快速排序比较时注意到的那样。

你对处理双数感兴趣吗?对于短序列，会有。调整块来处理计数是很棘手的，但它可以非常节省空间。

如果有一种方法可以减少有效“单词”的数量，进一步的压缩是可能的。

接下来，重新生成列表。

按顺序遍历64个桶，对于在该桶中找到的计数，生成该桶表示的序列的许多实例 当所有的桶都被迭代了，你就有了你的排序数组

一个4的序列，增加2位，所以有256个桶。 一个5的序列，增加了2位，所以有1024个桶 在某个时刻，桶的数量将接近您的限制。 如果从文件中读取序列，而不是将它们保存在内存中，那么桶将有更多的内存可用

我认为这将比在原地做排序更快，因为桶可能适合您的工作集。

这里有一个展示技巧的hack

#include <iostream>
#include <iomanip>


#include <math.h>


using namespace std;


const int width = 3;
const int bucketCount = exp(width * log(4)) + 1;
int *bucket = NULL;


const char charMap[4] = {'A', 'C', 'G', 'T'};


void setup
(
void
)
{
bucket = new int[bucketCount];
memset(bucket, '\0', bucketCount * sizeof(bucket[0]));
}


void teardown
(
void
)
{
delete[] bucket;
}


void show
(
int encoded
)
{
int z;
int y;
int j;
for (z = width - 1; z >= 0; z--)
{
int n = 1;
for (y = 0; y < z; y++)
n *= 4;


j = encoded % n;
encoded -= j;
encoded /= n;
cout << charMap[encoded];
encoded = j;
}


cout << endl;
}


int main(void)
{
// Sort this sequence
const char *testSequence = "CAGCCCAAAGGGTTTAGACTTGGTGCGCAGCAGTTAAGATTGTTT";


size_t testSequenceLength = strlen(testSequence);


setup();




// load the sequences into the buckets
size_t z;
for (z = 0; z < testSequenceLength; z += width)
{
int encoding = 0;


size_t y;
for (y = 0; y < width; y++)
{
encoding *= 4;


switch (*(testSequence + z + y))
{
case 'A' : encoding += 0; break;
case 'C' : encoding += 1; break;
case 'G' : encoding += 2; break;
case 'T' : encoding += 3; break;
default  : abort();
};
}


bucket[encoding]++;
}


/* show the sorted sequences */
for (z = 0; z < bucketCount; z++)
{
while (bucket[z] > 0)
{
show(z);
bucket[z]--;
}
}


teardown();


return 0;
}

你可以尝试使用单词查找树。对数据排序就是简单地遍历数据集并插入数据集;结构是自然排序的，你可以把它想象成类似于B-Tree(除了不做比较，你总是使用指针指向)。

缓存行为将有利于所有内部节点，因此您可能无法在此基础上进行改进;但是您也可以修改树的分支因子(确保每个节点都适合单个缓存线，将树节点分配为类似于堆的节点，作为表示级别顺序遍历的连续数组)。由于try也是数字结构(对于长度为k的元素，O(k)插入/查找/删除)，因此您的性能应该优于基数排序。

dsimcha的MSB基数排序看起来不错，但是Nils更接近问题的核心，他观察到缓存的局部性是在大问题规模下造成问题的原因。

我建议一个非常简单的方法:

1. 根据经验估计基数排序有效的最大大小m。
2. 一次读取m元素块，对它们进行基数排序，然后将它们写入(如果有足够的内存，则写入内存缓冲区，否则写入文件)，直到耗尽输入。
3. 归并排序结果排序块。

归并排序是我所知道的对缓存最友好的排序算法:“从数组A或B中读取下一项，然后将一项写入输出缓冲区。”它在磁带驱动器上有效运行。它确实需要2n空间来排序n项，但我敢打赌，你将看到的大大改进的缓存位置将使它变得不重要——如果你使用的是非就地基数排序，你无论如何都需要额外的空间。

最后请注意，归并排序可以在没有递归的情况下实现，事实上，这样做可以明确真正的线性内存访问模式。

看起来您已经解决了这个问题，但是为了记录，似乎有一种可行的就地基数排序是“美国国旗排序”。它的描述如下:工程基排序。一般的想法是对每个字符进行2次传递——首先计算每个字符有多少个，这样就可以将输入数组细分为箱子。然后再执行一遍，将每个元素交换到正确的bin中。现在递归地对每个箱子的下一个字符位置排序。

我将burstsort作为字符串的打包位表示。突发排序被认为比基数排序有更好的局部性，用突发尝试代替经典尝试减少了额外的空间使用。原始论文有测量。

基数排序不是缓存意识，也不是大集最快的排序算法。 你可以看看:

• ti7qsort。Ti7qsort是对整数最快的排序(可用于固定大小的小字符串)。
• Inline QSORT
• 字符串排序

您还可以使用压缩并将DNA的每个字母编码为2位，然后存储到排序数组中。

在性能方面，您可能希望查看更通用的字符串比较排序算法。

目前，您将触及每个字符串的每个元素，但您可以做得更好!

特别是，破裂的排序非常适合这种情况。另外，由于burstsort是基于try的，它对于DNA/RNA中使用的小字母非常有效，因为你不需要在trie实现中构建任何形式的三元搜索节点、散列或其他三节点压缩方案。这些尝试对于类似后缀数组的最终目标也很有用。

burstsort的一个不错的通用实现在源代码伪造的http://sourceforge.net/projects/burstsort/中可用——但它还不到位。

为了便于比较，http://www.cs.mu.oz.au/~rsinha/papers/SinhaRingZobel-2006.pdf基准测试中涵盖的C-burstsort实现在某些典型工作负载下比快速排序和基数排序快4-5倍。

你会想看看dr . 大规模基因组序列处理。笠原和森下。

由四个核苷酸字母A、C、G和T组成的字符串可以特别编码为Integers，以便多更快地处理。基数排序是书中讨论的许多算法之一;您应该能够适应这个问题的公认答案，并看到一个很大的性能改进。

"没有额外空间的基数排序"是一篇针对你的问题的论文。

虽然公认的答案完美地回答了问题的描述，但我已经到达了这个地方，徒劳地寻找一种算法将一个数组内联划分为N部分。我自己也写过一个，就是这个。

警告:这不是一个稳定的分区算法，因此对于多层分区，必须对每个结果分区重新分区，而不是对整个数组重新分区。优点是它是内联的。

它有助于解决所提出的问题的方法是，您可以根据字符串中的一个字母重复进行内联分区，然后在分区足够小时使用您选择的算法对分区进行排序。

  function partitionInPlace(input, partitionFunction, numPartitions, startIndex=0, endIndex=-1) {
if (endIndex===-1) endIndex=input.length;
const starts = Array.from({ length: numPartitions + 1 }, () => 0);
for (let i = startIndex; i < endIndex; i++) {
const val = input[i];
const partByte = partitionFunction(val);
starts[partByte]++;
}
let prev = startIndex;
for (let i = 0; i < numPartitions; i++) {
const p = prev;
prev += starts[i];
starts[i] = p;
}
const indexes = [...starts];
starts[numPartitions] = prev;
  

let bucket = 0;
while (bucket < numPartitions) {
const start = starts[bucket];
const end = starts[bucket + 1];
if (end - start < 1) {
bucket++;
continue;
}
let index = indexes[bucket];
if (index === end) {
bucket++;
continue;
}
  

let val = input[index];
let destBucket = partitionFunction(val);
if (destBucket === bucket) {
indexes[bucket] = index + 1;
continue;
}
  

let dest;
do {
dest = indexes[destBucket] - 1;
let destVal;
let destValBucket = destBucket;
while (destValBucket === destBucket) {
dest++;
destVal = input[dest];
destValBucket = partitionFunction(destVal);
}
  

input[dest] = val;
indexes[destBucket] = dest + 1;
  

val = destVal;
destBucket = destValBucket;
} while (dest !== index)
}
return starts;
}