根據距離原點的距離排序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通過這虛擬陣列，你會得到點的所有指標是距離原點最近距離最近

告訴我，如果有什麼是你不明白的。