已按坐标排序点的Graham扫描算法：是否需先按角度排序？

是的，Graham扫描必须先执行按参考点的极角排序的预处理步骤，直接用按x轴值排序的点列表无法正确完成凸包计算，你的示例尝试结论是对的。

核心原因 #

Graham扫描的核心逻辑是围绕一个选定的参考点（通常是y坐标最小的点，若有多个则选x坐标最小的），按极角从小到大遍历所有点，通过栈结构维护凸包的顶点：每次遍历到新点时，检查栈顶的两个点与当前点的转向（左转/右转/共线），以此判断是否需要弹出栈顶点来保证凸包的凸性。

如果改用x轴排序的点序列，遍历顺序完全不符合凸包的构建逻辑——这种排序无法保证点是围绕参考点按顺时针/逆时针方向依次遍历的，会导致栈无法正确筛选出凸包顶点，要么遗漏关键的凸包点，要么错误保留内部点。

对维基百科描述的补充说明 #

维基百科中提到的“若输入点已按某一坐标或相对固定向量的角度排序，则算法时间复杂度为O(n)”，这里的表述存在歧义。实际Graham扫描的O(n)时间复杂度前提，是输入已经完成了极角排序（基于参考点的相对角度），单纯的单一坐标排序（比如x轴、y轴）并不满足要求，不能替代极角排序的预处理步骤。

总结 #

Graham扫描的O(n log n)时间复杂度主要来自极角排序的预处理过程，只有当输入已经是极角排序好的状态时，后续的扫描过程才是线性时间O(n)。如果输入未排序，必须先执行极角排序，无法用单一坐标排序替代。

内容的提问来源于stack exchange，提问作者Rafael Almeida