二维凸包的算法使用排序 . 假设有人给你一个凸包实现为黑盒的库 . 展示如何使用凸包算法对给定整数序列进行排序 . 短语“黑匣子”意味着你不看内部代码;你只知道输入和输出是什么以及结果是什么样的 . 你不能从凸包的库实现中“拉出排序算法” . 您可以假设您可以将凸包算法称为原始步骤 .
对于来自输入序列A = [x1，...，xn]的整数的每个xi，n = | A |，创建其对应点（xi，xi ^ 2），然后在2D空间中组成n个点 . 这些点形成抛物线，它是凸曲线 . 在线性时间内，您可以检查点以检测最左侧的点pl，然后您可以从点pl到右侧遍历凸包，以生成数字x1，...，xn的排序顺序 .
因为Ω（n logn）是基于比较的排序的下限，我们可以认为凸包不小于其他排序可以比其下限更便宜，这将导致收缩 .
将整数视为位于x轴上的点（即y坐标为零） . 将点馈送到凸壳算法 . 如果算法不足以处理这种退化情况，则将每个整数分为两个点（x，1）和（x，-1） . 作为算法的输出，您将获得形成闭环（多边形）的点 . 绕过并找到具有最小x的点，之后增加的点的x值将表示排序的整数 .
同样，如果凸包算法在处理位于同一直线上的边界点时存在问题，则使用y值的平方整数来强调凸性 - 当然，如果所有整数都是非负的 . 如果存在负整数，则需要在计算y值的平方之前减去最小值 .
2 回答
对于来自输入序列A = [x1，...，xn]的整数的每个xi，n = | A |，创建其对应点（xi，xi ^ 2），然后在2D空间中组成n个点 . 这些点形成抛物线，它是凸曲线 . 在线性时间内，您可以检查点以检测最左侧的点pl，然后您可以从点pl到右侧遍历凸包，以生成数字x1，...，xn的排序顺序 .
因为Ω（n logn）是基于比较的排序的下限，我们可以认为凸包不小于其他排序可以比其下限更便宜，这将导致收缩 .
将整数视为位于x轴上的点（即y坐标为零） . 将点馈送到凸壳算法 . 如果算法不足以处理这种退化情况，则将每个整数分为两个点（x，1）和（x，-1） . 作为算法的输出，您将获得形成闭环（多边形）的点 . 绕过并找到具有最小x的点，之后增加的点的x值将表示排序的整数 .
同样，如果凸包算法在处理位于同一直线上的边界点时存在问题，则使用y值的平方整数来强调凸性 - 当然，如果所有整数都是非负的 . 如果存在负整数，则需要在计算y值的平方之前减去最小值 .