问题描述
我有一个名为Graph的class来表示一个连接的无向图，我想实现快速排序来根据边上的权重对边进行排序。
class Graph:
def __init__(self, n):
self.vertices = range(n)
self.edges = set([(random.random(), i, j) for i in xrange(n) for j in xrange(n)])
def qsort(self):
if len(self.edges) <= 1:
return self.edges
else:
return qsort([x for x in self.edges[1:] if x < self.edges[0]]) + [self.edges[0]] + qsort([x for x in self.edges[1:] if x >= self.edges[0]])
graph = Graph(10)
graph.qsort()
当我尝试运行上述程序时，出现NameError: global name 'qsort' is not defined 。
有人能告诉我我做错了什么吗？
1楼
您的问题的字面答案是您省略了self关键字： return self.qsort(...) + [self.edges[0]] + self.qsort(...) 。
看起来您正在尝试从实现类似 3-line qsort 的东西，也在给出。
你的实现是错误的，因为它应该有两个参数， self和你正在排序的数组。
不幸的是，没有办法避免传入数组，但有一个可能的解决方法。
向您的方法添加一个额外的关键字参数： qsort(self, arr = None) ，然后检查数组是否为None并在这种情况下使用self.edges 。
在这种情况下， graph.qsort()简洁语法graph.qsort()更改：
def qsort(self, arr = None):
if arr is None: arr = list(self.edges)
if len(arr) <= 1: return arr
else:
return self.qsort([x for x in arr[1:] if x < arr[0]]) + \
[arr[0]] + \
self.qsort([x for x in arr[1:] if x >= arr[0]])
请注意，因为self.edges是一个集合，所以除非您对输出数组执行某些操作，否则 qsort 方法基本上是无操作的。
集合不会改变。