sorting - 使用凸包算法对整数进行排序

Question

二维凸包的算法使用排序。假设有人给了你一个库，它的凸包实现为黑盒子。展示如何使用凸包算法对给定整数序列进行排序。短语“黑匣子”意味着您不查看代码内部；你只知道输入和输出是什么，结果是什么样子。您不能从凸包的库实现中“拉出排序算法”。您可以假设您可以将凸包算法称为原始步骤。

Answer 1

对于输入序列 A=[x1,...,xn] 的整数，n=|A| 中的每个 xi，创建其对应点 (xi, xi^2)，然后在 2D 空间中组合 n 个点。这些点形成抛物线，即凸曲线。在线性时间内，您可以检查点以检测最左边的点 pl，然后您可以从点 pl 开始向右遍历凸包，以产生数字 x1、...、xn 的排序顺序。

因为 Ω(n logn) 是基于比较的排序的下限，我们可以争辩说，凸包占用的时间不少于否则排序可能比其下限更便宜，这将导致收缩。

Answer 2

将整数视为位于 x 轴上的点（即 y 坐标为零）。将点馈送到凸包算法。如果算法不够健壮，无法处理这种退化情况，请将每个整数分为两个点 (x, 1) 和 (x, -1)。作为算法的输出，您将获得形成闭环（多边形）的点。四处寻找x最小的点，然后点的x值增加将代表排序的整数。

同样，如果凸包算法在处理位于同一直线上的边界点时存在问题，请使用 y 值的平方整数来强调凸性 - 当然，如果所有整数都是非负的。如果存在负整数，则需要在计算 y 值的平方之前减去最小值。