按升序或降序排序(任意选择;优先选择哪个更便宜)

Question

我有一系列元素.这个数组可能是:

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

但我不知道(提前)这些案件中适用哪一种.我更愿意将数组排序为它已经接近的顺序.

无论输出是升序还是降序都无关紧要,但它必须是一个或另一个(所以我可以对它进行二进制搜索.)

排序不一定稳定.

---

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

• 填充数组
• 按某些属性A排序
• 做一些处理(计算分位数,和其他一些小东西)
• 排序其他一些属性B.
• 做更多的处理
• 按属性C排序
• 做更多的处理

A和B通常彼此相关(但可能是正面的或负面的.)同样适用于B和C.偶尔A == C.

*"几乎排序"在这里意味着大多数元素都接近其最终位置.但很少完全处于最终位置(存在大量的加性噪声​​,并且没有很多长的排序子序列.)但是,在阵列的开始和结束处通常会有一些"异常值",它们是订单的不良预测因子.下一种. 

---

是否有一种算法可以利用我不喜欢升序与降序的事实,以便更便宜地排序(与我目前正在使用的TimSort相比？)

Answer 1

我将继续使用 Timsort （但是，一个不错的替代方案是Smoothsort ^*），但首先探测数组以决定是否按升序或降序排序。查看第一个和最后一个元素并相应地排序。如果数组未排序，则选择并不重要；如果它是（部分）排序的，则以较宽的间隔进行探测更有可能正确检测到哪种方式。

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