如何对有序序列数组进行有效排序
我正在实现复杂的算法，其中一部分是对有序数字序列的数组进行排序。整个算法应该是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到数百 不再
- long，数组
- 可以是 100k 长，可能不再有 C++ 中的最终实现，但现在它可能不重要了，
您能建议我排序的最佳方法吗？多谢
I am implementing the complex algorithm which part is sorting array of ordered sequences of numbers. The whole algorithm should be nlog(n) complexity, so this part should be same or better but I don't know how to do this.
There is an example. There is an array of sequences:
(0)
(0,1)
(0)
(0,5)
(2,4)
()
(0,5)
()
(2,4)
(1,3,4)
and final sort should be:
()
()
(0)
(0)
(0,1)
(0,5)
(0,5)
(1,3,4)
(2,4)
(2,4)
There are some important notes:
- sorting is lexicographical
- sequences are ordered but there is no guarantee for continuousness
- there are also empty sequences
- there is a lot of identical sequences
- sequences are from 0 to hundreds long, no more
- the array can be 100k long, probably no more
- final implementation will be in C++ but now it is not probably important
Can you suggest me the best way how to sort it, please? Thanks a lot
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
您的问题似乎类似于
基数排序，在这种情况下，首先对您的按最右边的项目（例如第 100 个项目）排序，如果不存在此类项目，请将其设置为min possible value - 1（例如，在我可以看到 -1 的情况下），然后对这个排序序列进行排序最右边的第二个项目，然后继续这样。另外，如果序列中的项目都在 1..k 之间（在本例中我可以看到有 1..9 之间），请使用
计数排序在O(n)内对它们进行排序，如果可以使用计数排序，则排序时间为O(n)，否则排序时间为O(n log n).Your problem seems similar to
radix sort, in this case first sort your sequences by rightmost item (for example 100th item) if no such item exists, set it asmin possible value - 1(for example in the case I can see -1) , then sort this sorted sequence with second rightmost item, and continue this way.Also if items in sequences all are between 1..k (in this case I can see there are between 1..9) use
counting sortto sort them in O(n), if you can use counting sort, the sorting time is O(n) but else the sorting time is O(n log n).如果使用快速排序，则排序算法将为 O(n log n)。如何比较这两个项目与排序本身的复杂性无关，并且有其自身的复杂性（大概是 O(m)）。
If you use quicksort, then the sort algorithm will be O(n log n). How you have to compare the two items is irrelevant to complexity of the sort itself, and has its own complexity (presumably O(m)).
如果您可以将 GPLv3 代码集成到您的项目中，GNU Sort 可能是一个不错的起点。至少，当我在您的示例输入上运行它时，我得到了您的示例输出，因此它不会立即错误。
If you can integrate GPLv3 code into your project, GNU Sort might be a good place to start. At least, when I ran it on your sample input, I got your sample output, so it's not immediately wrong.