正如MBo正确指出的那样，您的问题是构造输入列表的后缀数组的问题。快速而复杂的算法实际上是线性时间，但是由于您只是针对O(n log n)，所以我将尝试提出一个更易于实现的简单版本。

基本思想和初步O(n log² n)实施

让我们以序列[4, 2, 2, 1]为例。它的后缀是

0: 4 2 2 1
1: 2 2 1
2: 2 1
3: 1

我用原始序列中的后缀索引了后缀。最终，我们希望按字典顺序对这组后缀进行快速排序。我们知道可以在恒定空间中使用其后缀索引来表示每个后缀，并且可以O(n log n)使用合并排序，堆排序或类似算法在比较中进行排序。因此问题仍然存在，我们如何快速比较两个后缀？

假设我们要比较后缀[2, 2, 1]和[2, 1]。我们可以填充负无穷大值的值，以更改比较结果：[2, 2, 1, -∞]和[2, 1, -∞, -∞]。

现在，这里的主要思想是以下分而治之的观察：而不是逐个字符地比较序列，直到找到两个不同的位置，我们可以将两个列表一分为二并按字典顺序比较两半：

     [a, b, c, d]     < [e, f, g, h] 
 <=> ([a, b], [c, d]) < ([e, f], [g, h])
 <=> [a, b] < [e, f] or ([a, b,] = [e, f] and [c, d] < [g, h])

本质上，我们已经将比较序列的问题分解为比较较小序列的两个问题。这导致以下算法：

步骤1 ：对长度为1的子字符串（连续的子序列）进行排序。在我们的示例中，长度为1的子字符串为[4], [2], [2], [1]。每个子字符串都可以由原始列表中的起始位置表示。我们通过简单的比较排序对它们进行排序并得到[1], [2], [2], [4]。我们通过在列表的排序列表中分配其排名的每个位置来存储结果：

position   substring   rank
0          [4]         2
1          [2]         1
2          [2]         1
3          [1]         0

重要的是，我们将相同的等级分配给相等的子字符串！

步骤2：
现在我们要对长度为2的子字符串进行排序。实际上只有3个这样的子字符串，但是如果需要的话，我们通过填充负无穷大为每个位置分配一个。这里的窍门是，我们可以使用上面的“分而治之”的想法以及在步骤1中分配的等级来进行快速比较（这实际上不是必需的，但稍后将变得很重要）。

position  substring    halves        ranks from step 1   final rank
0         [4,  2]      ([4], [2])    (2,  1)             3               
1         [2,  2]      ([2], [2])    (1,  1)             2
2         [2,  1]      ([2], [2])    (1,  0)             1
3         [1, -∞]      ([1], [-∞])   (0, -∞)             0

步骤3： 您猜对了，现在我们对长度为4（！）的子字符串进行排序。这些恰好是列表的后缀！这次我们可以使用分治法和第二步的结果：

position  substring         halves              ranks from step 2   final rank
0         [4,  2,  2,  1]   ([4, 2], [2,  1])   (3,  1)             3
1         [2,  2,  1, -∞]   ([2, 2], [1, -∞])   (2,  0)             2
2         [2,  1, -∞, -∞]   ([2, 1], [-∞,-∞])   (1, -∞)             1
3         [1, -∞, -∞, -∞]   ([1,-∞], [-∞,-∞])   (0, -∞)             0

大功告成！如果我们的初始序列具有si​​ze 2^k，那么我们将需要一些k步骤。或者反过来说，我们需要一些log_2 n步骤来处理一系列size
n。如果其长度不是2的幂，则仅填充负无穷大。

对于实际的实现，我们只需要记住算法每一步的序列“最终排名”。

C ++中的实现可能看起来像这样（使用编译-std=c++11）：

#include <algorithm>
#include <iostream>
using namespace std;

int seq[] = {8, 3, 2, 4, 2, 2, 1};
const int n = 7;
const int log2n = 3;       // log2n = ceil(log_2(n))
int Rank[log2n + 1][n];    // Rank[i] will save the final Ranks of step i
tuple<int, int, int> L[n]; // L is a list of tuples. in step i,
                           // this will hold pairs of Ranks from step i - 1
                           // along with the substring index
const int neginf = -1;     // should be smaller than all the numbers in seq
int main() {
  for (int i = 0; i < n; ++i)
    Rank[1][i] = seq[i]; // step 1 is actually simple if you think about it
  for (int step = 2; step <= log2n; ++step) {
    int length = 1 << (step - 1); // length is 2^(step - 1)
    for (int i = 0; i < n; ++i)
      L[i] = make_tuple(
                Rank[step - 1][i],
                (i + length / 2 < n) ? Rank[step - 1][i + length / 2] : neginf,
                i); // we need to know where the tuple came from later
    sort(L, L + n); // lexicographical sort
    for (int i = 0; i < n; ++i) {
      // we save the rank of the index, but we need to be careful to
      // assign equal ranks to equal pairs
      Rank[step][get<2>(L[i])] = (i > 0 && get<0>(L[i]) == get<0>(L[i - 1])
                                        && get<1>(L[i]) == get<1>(L[i - 1]))
                                    ? Rank[step][get<2>(L[i - 1])] 
                                    : i;
    }
  }
  // the suffix array is in L after the last step
  for (int i = 0; i < n; ++i) {
    int start = get<2>(L[i]);
    cout << start << ":";
    for (int j = start; j < n; ++j)
      cout << " " << seq[j];
    cout << endl;
  }
}

输出：

6: 1
5: 2 1
4: 2 2 1
2: 2 4 2 2 1
1: 3 2 4 2 2 1
3: 4 2 2 1
0: 8 3 2 4 2 2 1

的复杂度为O(log n * (n + sort))，这是O(n log² n)在此实现中的原因，因为我们使用了一种比较复杂性O(n log n)

一个简单的O(n log n)算法

如果我们设法在O(n)每个步骤中进行排序，那么我们将O(n log n)受到限制。因此，基本上我们必须对一对序列进行排序(x, y)，其中0 <= x, y < n。我们知道，我们可以O(n)使用计数sort在给定范围内及时对整数序列进行排序。我们可以将对解释(x, y)为z = n * x + y以n
为底的数字。现在我们可以看到如何使用LSD基数排序对。实际上，这意味着我们通过y使用计数排序增加对数对进行排序，然后
再次 使用计数排序对增加进行排序x。由于计数排序是稳定的，因此这给了我们对中的字典顺序2 * O(n) = O(n)。因此，最终的复杂度是O(n log n)。

如果您有兴趣，可以在我的Github存储库中找到O(n log² n)该方法的实现。该实现有27行代码。整洁，不是吗？