algorithm - 如何有效地对有序序列数组进行排序

Question

我正在实现复杂的算法，其中一部分是对有序数字序列的数组进行排序。整个算法应该是nlog(n) 复杂度，所以这部分应该相同或更好，但我不知道该怎么做。

有一个例子。有一个序列数组:

(0)
(0,1)
(0)
(0,5)
(2,4)
()
(0,5)
()
(2,4)
(1,3,4)

最后的排序应该是:

()
()
(0)
(0)
(0,1)
(0,5)
(0,5)
(1,3,4)
(2,4)
(2,4)

有一些重要的注意事项:

• 按字典顺序排序
• 序列是有序的，但不能保证连续性
• 也有空序列
• 有很多相同的序列
• 序列长度从0到数百不等
• 数组可以有 100k 长，可能不会更多
• 最终实现将使用 C++，但现在它可能并不重要

你能建议我最好的排序方式吗？非常感谢

Answer 1

您的问题似乎类似于 radix sort ，在这种情况下，首先按最右边的项目(例如第 100 项)对序列进行排序，如果不存在此类项目，则将其设置为 min possible value - 1(例如，在我可以看到 -1 的情况下) , 然后用最右边的第二个项目对这个排序序列进行排序，并继续这样。

此外，如果序列中的项目都在 1..k 之间(在这种情况下，我可以看到在 1..9 之间)使用 counting sort在O(n)中对它们进行排序，如果可以使用计数排序，则排序时间为O(n)，否则排序时间为O(n log n)。