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)。

Answer 2

如果您使用快速排序，那么排序算法将是 O(n log n)。如何比较这两个项目与排序本身的复杂性无关，并且有其自身的复杂性（大概是 O(m)）。

Answer 3

如果您可以将 GPLv3 代码集成到您的项目中，那么GNU Sort可能是一个不错的起点。至少，当我在您的示例输入上运行它时，我得到了您的示例输出，所以它不会立即出错。