use*_*677 5 sorting algorithm tree performance kdtree
我正在尝试使用 KD 树来平衡一组 (Million +) 3D 点，我有两种方法可以做到。
方式一：
使用 O(n) 算法沿给定轴查找数组大小/第 2 个最大元素并将其存储在当前节点
迭代向量中的所有元素，对于每个元素，将它们与我刚刚找到的元素进行比较，并将较小的放在 newArray1 中，将较大的放在 newArray2 中
递归
方式二：
使用快速排序 O(nlogn) 沿给定轴对数组中的所有元素进行排序，获取位置 arraysize/2 的元素并将其存储在当前节点中。
然后将索引 0 到 arraysize/2-1 的所有元素放入 newArray1，将 arraysize/2 到 arraysize-1 的所有元素放入 newArray2
递归
方式 2 看起来更“优雅”，但方式 1 似乎更快，因为中位数搜索和迭代都是 O(n)，所以我得到 O(2n)，它只是减少到 O(n)。但同时，即使方式2是O(nlogn)的排序时间，将数组拆分为2可以在恒定时间内完成，但这是否弥补了O(nlogn)的排序时间？
我该怎么办？或者有没有更好的方法来做到这一点，我什至没有看到？
方式3怎么样：
使用 O(n) 算法（例如 QuickSelect）来确保位置 length/2 处的元素是正确的元素，之前的所有元素都小于它，而后面的所有元素都比它大（无需完全排序！） - 这可能是无论如何，你在方式 1 步骤 1 中使用的算法......
递归到每一半（中间元素除外）并重复下一个轴。
请注意，您实际上不需要创建“节点”对象。实际上，您可以将树保存在一个大数组中。搜索时，从第一个轴的 length/2 处开始。
我见过 ELKI 使用这个技巧。它使用很少的内存和代码，这使得树非常快。