kd樹籌建排序優化

Question

在Python編程語言實現的kd樹的算法構建如下（從http://en.wikipedia.org/wiki/K-d_tree）：

class Node: pass 

def kdtree(point_list, depth=0): 

    if not point_list: 
    return None 

    # Select axis based on depth so that axis cycles through all valid values 
    k = len(point_list[0]) # assumes all points have the same dimension 
    axis = depth % k 

    # Sort point list and choose median as pivot element 
    point_list.sort(key=lambda point: point[axis]) 
    median = len(point_list) // 2 # choose median 

    # Create node and construct subtrees 
    node = Node() 
    node.location = point_list[median] 
    node.left_child = kdtree(point_list[:median], depth + 1) 
    node.right_child = kdtree(point_list[median + 1:], depth + 1) 
    return node 

則排序基於每一步進行。如何減少排序的數量？

Answer 1

它看起來像你只是排序分裂中位數。相反，您可以實現線性時間選擇算法，如quickselect，然後執行point_list的線性時間分區。那麼，你根本不需要再分類了。