根据距离原点的距离排序2d点

Question

我需要编写一个ac代码，它将从距离原点最近的点 的点到与原点距离最大的点的随机数2d个点进行排序。我需要有一个n * log（n）的时间复杂度，其中n是我们从用户获得的点的数量，我想使用堆排序方法。唯一的问题是通过等式（x，y和（0,0）即sqrt（（x^2）+（y^2））之间的距离并将此公式应用于我使用的排序方法。只需寻找一些提示或任何关于如何我是否继续从这里，所以我会很感激 一条建议

Answer 1

任何好的比较排序算法将运行在O（ n log n）。为了提高效率，您希望比较器尽可能快地运行。一个想法是：比较x^2+y^2而不是实际的距离。另一种方法是：为每个点计算一次数量并将其缓存到点对象或其他位置，而不是为每次比较重新计算。

Answer 2

堆排序解决方案：

1.创建从原点的每个点的距离的最大堆。

2.假设你正在通过数组实现堆，则只需创建一个包含该点索引的虚拟数组。

3.just正常堆排序&当您在索引之间进行交换时，也交换虚拟数组中的相同索引。

lets say my input from user is following point  
1,0 
8,6 
4,4 
6,0 

所以我的距离数组将包含距离

1,10,sqrt(32),6 

我的虚拟阵列将包含每个点的正常指数

1,2,3,4 

现在装箱它的阵列会后创造最大堆 10,6,sqrt(32),1 所以那时候你的哑数组看起来就像 2,4,3,1。 现在应用堆排序10将与1交换以及2将 在虚拟阵列&等等......

交换用1通过这虚拟阵列，你会得到点的所有指标是距离原点最近距离最近

告诉我，如果有什么是你不明白的。