排序并将一部分排序的阵列 [英] Sort an array which is partially sorted

问题描述

我想整理其中有属性，如

I am trying to sort an array which has properties like

它增加高达一定程度那么它开始下降，则增大后减小等等。有没有什么算法，可以通过使用它被部分下令小于n日志（n）的复杂性进行排序呢？

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?

数组示例= 14,19,34,56,36,22,20,7,45,56,50,32,31,45 .........高达ñ

array example = 14,19,34,56,36,22,20,7,45,56,50,32,31,45......... upto n

在此先感谢

推荐答案

您能找到的变化/分区点，对分区之间进行合并排序。这将利用现有订货的优势，为常合并排序与对元素的开始。

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.

修改只是想在这里找出复杂性。合并排序为n的log（n），其中的log（n）涉及必须重新分区的次数。首先每对元素，那么每对对等......直到到达数组的大小。在这种情况下，你必须与对分区，其中p＆LT n个元素; N，所以我猜的复杂性为p数（P），但乐于接受改正。例如合并各对paritions的，并且基于该合并后一半的分区数重复

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.

这篇关于排序并将一部分排序的阵列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！