对部分排序的数组进行排序
我正在尝试对一个数组进行排序，该数组具有以下属性：
先增加到一定程度，然后开始减少，然后增加，然后减少，依此类推。是否有任何算法可以通过利用部分排序来以低于 nlog(n) 的复杂度对其进行排序？
数组示例 = 14,19,34,56,36,22,20,7,45,56,50,32,31,45......... 最多 n
提前致谢
I am trying to sort an array which has properties like
it increases upto some extent then it starts decreasing, then increases and then decreases and so on. Is there any algorithm which can sort this in less then nlog(n) complexity by making use of it being partially ordered?
array example = 14,19,34,56,36,22,20,7,45,56,50,32,31,45......... upto n
Thanks in advance
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（5）
任何数字序列都会向上和向下、再次向上和向下等等，除非它们已经完全排序（当然可以从向下开始）。您可以遍历序列，注意它改变方向的点，然后对序列进行合并排序（反向读取向后序列）。
一般来说，复杂性是 N log N，因为我们不知道此时它是如何排序的。如果它排序得比较好，即方向变化较少，则需要的比较就会较少。
Any sequence of numbers will go up and down and up and down again etc unless they are already fully sorted (May start with a down, of course). You could run through the sequence noting the points where it changes direction, then then merge-sort the sequences (reverse reading the backward sequences)
In general the complexity is N log N because we don't know how sorted it is at this point. If it is moderately well sorted, i.e. there are fewer changes of direction, it will take fewer comparisons.
您可以找到更改/分区点，并在分区对之间执行合并排序。这将利用现有的排序，因为通常合并排序从元素对开始。
编辑只是想弄清楚这里的复杂性。归并排序是 n log(n)，其中 log(n) 与必须重新分区的次数相关。首先是每对元素，然后是每对元素，依此类推......直到达到数组的大小。在这种情况下，您有 n 个元素和 p 个分区，其中 p < n，所以我猜测复杂度是 p log(p)，但我愿意纠正。例如，合并每对分区，并在合并后基于一半的分区数重复。
You could find the change / partition points, and perform a merge sort between pairs of partitions. This would take advantage of the existing ordering, as normally the merge sort starts with pairs of elements.
Edit Just trying to figure out the complexity here. Merge sort is n log(n), where the log(n) relates to the number of times you have to re-partition. First every pair of elements, then every pair of pairs, etc... until you reach the size of the array. In this case you have n elements with p partitions, where p < n, so I'm guessing the complexity is p log(p), but am open to correction. e.g. merge each pair of paritions, and repeat based on half the number of partitions after the merge.
请参阅拓扑排序
See Topological sorting
如果您知道数据“几乎已排序”并且集合大小相当小（例如可以通过 16 位整数索引的数组），那么 Shell 可能是您最好的选择。是的，它的基本时间复杂度为 O(n^2)（可以通过用于间隙大小调整的序列将其降低到当前最好-最坏情况的 O(n*log^2(n))），但是在已排序的集合上，随着输入集的排序达到 O(n) 的最佳情况，性能会得到提高。当输入未按您预期的方式排序时，使用 Sedgewick 序列来确定间隙大小将提供最佳性能。
If you know for a fact that the data are "almost sorted" and the set size is reasonably small (say an array that can be indexed by a 16-bit integer), then Shell is probably your best bet. Yes, it has a basic time complexity of O(n^2) (which can be reduced by the sequence used for gap sizing to a current best-worst-case of O(n*log^2(n))), but the performance improves with the sortedness of the input set to a best-case of O(n) on an already-sorted set. Using Sedgewick's sequence for gap size will give the best performance on those occasions when the input is not as sorted as you expected it to be.
链排序可能与您正在寻找的内容很接近。平均情况为 O(n sqrt(n))，最佳情况为 O(n)（列表已排序），最坏情况为 O(n^2)（列表按相反顺序排序）。
分享并享受。
Strand Sort might be close to what you're looking for. O(n sqrt(n)) in the average case, O(n) best case (list already sorted), O(n^2) worst case (list sorted in reverse order).
Share and enjoy.