Python中浮点数数组的字典序排序

Question

好的，我有一个4x2的numpy ndarray，我想按字典顺序对其进行排序。也就是说，如果我有以下数组

[[0,0],
[1,1],
[0,1],
[1,0]]

我希望它成为

[[0,0],
[0,1],
[1,0],
[1,1]]

我该如何操作？

- Pedro Carvalho

---

对于普通的列表，可以使用l.sort()来完成。 - Bhargav Rao

似乎不起作用。执行l.sort()会将[[2,1],[0,2]]转换为[[1,2],[0,2]]，而不是[[0,2],[2,1]]（当它是一个ndarray时）。 - Pedro Carvalho

l.sort() 只能对普通列表进行排序，而不能对 numpy 数组进行排序。例如，l = [[2,1], [0,2]] 经过 l.sort() 后会变成 [[0, 2], [2, 1]]。 - Bhargav Rao

Answer 1

你可以使用numpy的lexsort。然而，lexsort使用最后一列作为主键进行排序。获得所需结果的一种方法是明确指定列：

 x[np.lexsort((x[:,1], x[:,0]))]

 # array([[0, 0],
 #   [0, 1],
 #   [1, 0],
 #   [1, 1]])

- tom10

---

你知道这个的时间复杂度是多少吗？ - Pedro Carvalho

@PedroCarvalho：对于一个 h*w 的数组，最坏情况下的性能是 O(h*w*log(h))，因为它是在长度为 h 的输入上进行比较排序，其中比较可能需要最坏 O(w) 的时间。如果行通常在前几列中不同，则预期性能将为 O(h*log(h))，因为比较将需要预期 O(1) 的时间。 - user2357112

另外，与其逐个列出列，您可以执行 x[np.lexsort(x.T[::-1])]。（但这仍然是太多的中间步骤，仅仅进行词典排序。NumPy 的排序 API 似乎被组合成一种非常奇怪的方式。） - user2357112