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

Question

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

Answer 1

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

\n\n

因为 \xce\xa9(n logn) 是基于比较的排序的下限，所以我们可以认为凸包所花费的时间不少于，否则排序可以比其下限更便宜，这将导致收缩。

\n