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

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

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

特别地，爆发排序非常适合这种情况。另外，由于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倍。

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

原因:

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

我知道这不能直接回答您的问题，但是如果排序是一个瓶颈，那么您可能想要看看作为预处理步骤的近似排序算法(软堆上的wiki-page可以让您开始)。

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

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

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

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

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

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

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

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

您当然可以通过对序列进行位编码来降低内存需求。 你看到的是排列，对于长度为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;
}