排序排列的是部分地排序

它增加高达一定程度那么它开始减小，则增大后减小等特性的阵列。有没有任何算法可以通过使用部分有序的方法将它分类为nlog（n）以下的复杂度？

阵列示例= 14,19,34,56,36,22,20,7,45,56,50,32,31,45 .........高达Ñ

由于提前

2010-10-21 peloooo

您可以找到更改/分区点，并在分区对之间执行合并排序。这将利用现有的顺序，因为合并排序通常以成对的元素开始。

编辑只是想弄清楚这里的复杂性。合并排序是n log（n），其中log（n）与您必须重新分区的次数相关。首先是每一对元素，然后是每对对，等等......直到达到数组的大小。在这种情况下，你有n个具有p个分区的元素，其中p < n，所以我猜测复杂度是p log（p），但我可以纠正。例如合并每对分区，并根据合并后分区数量的一半重复。

来源

2010-10-21 09:27:15

在相似的线条上，我认为1）注意方向改变的所有点。 2）我们可以很容易地通过反转来增加递减顺序，对于n个元素依次取O（n）。 3）现在我们有一个数组，每个元素只改变一个方向。 4）注意到这些我们可以应用合并 – peloooo 2010-10-21 09:36:07

任何指向合并排序的样本实现，高效的内存移动次数和额外的内存？ – Dummy00001 2010-10-21 10:51:20

谷歌合并排序提出了大量的例子。我通常会使用数组，而我的偏好是就地排序并使用迭代而不是递归。对于所问的问题，这非常简单。找到两个相邻的正向和反向序列。将它们合并为一个正向序列。对数组中的所有序列对重复。从数组开始重复，直到没有更多的序列。就地合并仅涉及将元素从一个序列交换到另一个序列，其中第二个序列上的光标元素小于第一个序列中的元素。 – 2010-10-21 12:14:15

见Topological sorting

来源

2010-10-21 09:30:20 stacker

哦，这已经在这里提到：http://stackoverflow.com/questions/480640/what-is-the-best-way-to-sort-a-partially-ordered-list – stacker 2010-10-21 09:30:54

的任意序列会等走向上和向下向上和向下再次除非它们已经完全排序（可能用下来开始，当然）。你可以运行序列记录它改变方向的点，然后合并排序序列（反向读取反向序列）

一般来说，复杂度是N log N，因为我们不知道它是如何排序的在此刻。如果排序适中，即方向变化较少，则比较次数会减少。

来源

2010-10-21 09:31:54 CashCow

鉴于开放性问题具体说明数据是部分排序的，我想我们需要量化这个以便从n log（n）移开。最简单的方法是计算方向上的分区/更改，我们可以将其称为p。在这种情况下，复杂度变成p log（p）。如果n与p成比例，例如p = n/K其中K是常数，复杂度在技术上仍然是n log（n），尽管排序会更快。如果p> n/2，则部分排序的数据的先决条件未被满足。 – 2010-10-21 10:59:03

如果我们知道它的部分排序的性质，那么我们可以但我们没有告知这一点。鉴于规范所说的不过是事实上有些地区在上升，而其他地区则在下降，我们对它的分类完全一无所知，任何数据序列都符合规范。因此，或者没有比O（N log N）更一般的算法，或者如果你非常聪明并且提出了一个算法，那么你将在历史中下降，因为它将是一种通用的排序算法！ – CashCow 2010-10-22 11:18:36

尽管我很喜欢在历史中走下坡路，但通用O（n）排序已经存在了一段时间，但在很多情况下占用了太多的空间。对于给出的样本数据，鸽子分类可以很好地工作，请参阅http://en.wikipedia.org/wiki/Pigeonhole_sort有时您需要寻求关于规格的说明，而不是将其作为福音。这个问题是根据部分排序的数据提出的，因此我期望在答案中量化和利用这一点， – 2010-11-16 07:34:03

如果您知道数据“几乎排序”并且设置的大小相当小（例如可以用16位整数索引的数组），那么Shell可能是您最好的选择。是的，它具有O（n^2）的基本时间复杂度（其可以通过用于间隙调整的序列减少到O（n * log^2（n））的当前最坏情况），但是在已经排序的集合上，输入的排序设置为O（n）的最佳情况，性能提高。使用Sedgewick的间隔大小序列可以在输入不像您预期的那样排序的情况下获得最佳性能。

来源

2010-10-21 10:26:58

Strand Sort可能接近你要找的东西。 O（n sqrt（n）），O（n）最好的情况（已经排序的列表），O（n^2）最差的情况（列表按照相反顺序排序）。

分享和享受。

来源

2010-10-21 10:33:32

排序排列的是部分地排序

回答

相关问题