5

我有一个元素数组。这个数组可以是：

  • 随机洗牌（大约 20% 的时间）
  • 几乎按升序排序*（大约 40% 的时间）
  • 几乎按降序排序（大约 40% 的时间）

但我不知道（提前）这些案例中的哪一个适用。我更愿意将数组排序为它已经接近的顺序。

输出是升序还是降序无关紧要，但它必须是一个或另一个（所以我可以对其执行二进制搜索。）

排序不必是稳定的。

一些背景信息：该过程大致如下：

  • 填充数组
  • 对某个属性 A 进行排序
  • 做一些处理（计算分位数和其他一些小东西）
  • 按其他属性 B 排序
  • 做更多的处理
  • 按属性 C 排序
  • 做更多的处理

A 和 B 通常相互关联（但可能是正的或负的）。同样适用于 B 和 C。偶尔 A == C。

* 这里的“几乎排序”意味着大多数元素都接近它们的最终位置。但很少准确地位于它们的最终位置（有很多附加噪声，并且没有多少长排序的子序列。）仍然，在数组的开头和结尾通常有一些“异常值”，它们是顺序的不良预测指标下一种。 

有没有一种算法可以利用我不偏好升序和降序这一事实，以更便宜地进行排序（与我目前使用的 TimSort 相比？）

4

2 回答 2

3

我会继续使用 Timsort （但是，一个很好的选择是Smoothsort *），但首先探测数组以决定是按升序还是降序排序。查看第一个和最后一个元素并进行相应的排序。如果数组未排序，则选择无关紧要；如果它是（部分）排序的，则以较宽的间隔进行探测更有可能正确检测到哪种方式。

* Smoothsort 与 Timsort 具有相同的最佳、平均和最坏情况时间，以及更好的空间复杂度。与 Timsort 一样，它专门设计用于利用部分排序的数据。

于 2012-11-03T23:17:12.163 回答
2

另一种考虑的可能性：

  • 开始进行（手动）插入排序
  • 当你走的时候，计算你执行的反转次数
  • 在您完成了一些固定的少量插入后，将您计算的反转次数与如果数据开始反向排序到该点将发生的最大反转次数进行比较：
  • 如果该比例接近 0，则（可能）数据接近排序。完成插入排序，它在几乎排序的数据上表现得非常好。如果你不喜欢“可能”的声音，那么继续计算反转，如果它低于阈值，则准备好回退到 Timsort。
  • 如果比例接近 1，那么（可能）数据几乎是反向排序的，并且您在开始时有少量排序的元素。将它们移到最后，将它们反转，并使用反向比较器完成插入排序。
  • Otherwise the data is random, use your favourite sorting algorithm. I'd say Timsort, but since that does well on nearly-sorted data there must be some other algorithm that does at least a tiny bit better than Timsort does on uniformly-shuffled data. Probably plain merge sort without the Tim.

The "small fixed number" can be a number for which insertion sort is fairly fast even in bad cases. I would guess 10-20 or so. It's possible to work out the probability of a false positive in uniformly shuffled data for any given number of insertions and any given threshold of "close to 0/1", but I'm too lazy.

You say the first and last few array elements typically buck the trend, in which case you could exclude them from the initial test insertion sort.

显然，这种方法在某种程度上受到了 Timsort 的启发。但是 Timsort 对包含运行的数据进行了极其优化——我试图只对接近一次大运行（在任一方向）的数据进行极其优化。Timsort 的另一个特点是它经过了很好的测试，我不声称要分享这一点。

于 2012-11-03T23:35:17.020 回答