这是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倍。

您当然可以通过对序列进行位编码来降低内存需求。 你看到的是排列，对于长度为2的“ACGT”有16个状态，或4个比特。 长度为3，即64个状态，可以用6位编码。所以它看起来像序列中的每个字母2位，或者像你说的16个字符大约32位。

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

对于长度为3的序列，可以创建64个桶，大小可能是uint32或uint64。 将它们初始化为零。 遍历你非常非常大的3个字符序列列表，并像上面那样编码它们。 使用这个作为下标，并增加该桶。 重复这一步骤，直到所有的序列都处理完毕。

接下来，重新生成列表。

按顺序遍历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;
}

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

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

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

burstsort的一个不错的通用实现可以在源代码forge (http://sourceforge.net/projects/burstsort/)上找到——但还不到位。

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

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

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

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

虽然公认的答案完美地回答了问题的描述，但我已经到达了这个地方，徒劳地寻找一种算法将一个数组内联划分为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;
  }

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

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

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

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

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

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

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

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

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