我有一个点的列表，其中每个点都是 * d维 *。该列表当前使用常规的list.sort()函数排序，这意味着键的优先级从第一个维度到最后一个维度。我想获取该列表并对其排序，同时优先考虑第二个键，在其上运行代码，然后对第三个键进行优先级排序，以此类推。有没有比对特定键使用sort（）函数更有效的方法？
因为我知道在每一步中，点的排序优先于第k维，并且我想按下一个维排序，所以我认为可以管理列表并对其排序，就像在O中组合一堆排序列表一样（n）而不是O（nlogn）。这是可能的，还是我弄错了？如果可能的话，在python中实现的帮助将是非常感谢的。
- 编辑：**
list.sort()函数后的列表示例：
[(-3, -5, -5, -2), (-3, -4, 2, -2), (-3, 2, 5, 2), (0, 0, -5, 1), (1, -3, 2, 0), (2, -1, 0, 0), (2, 3, -1, 0), (4, 1, -2, 1), (5, -3, -1, 1), (5, 1, -2, -2)]
3条答案
按热度按时间ssm49v7z1#
您可以尝试：
disbfnqx2#
想象一下，你可以在
O(k.n lgn)以内的维度上对n元素排序k次，例如O(n (lg n + k-1))（先在O(n lg n)中排序第一个维度，然后在O(n)中排序）。然后取一个
m数字列表，将其拆分为sqrt(m)块（大致）sqrt(m)个元素。您有k = n = sqrt(m)。（就像Python中一样）块。由于sqrt优于lg，您的块按O(m)排序。您有sqrt(m)排序列表，可以将其合并到O(n lg k) = O(sqrt(m) lg (sqrt(m)))中（https://en.wikipedia.org/wiki/K-way_merge_algorithm）。此合并时间小于O(m)。将这些块放在一起，您的列表将按O(m)排序。O (n lg n)边界被普遍接受，因此可以合理地说，您不会找到一种方法来实现少于O(k.n lgn)的k排序。oalqel3c3#
参考：https://docs.python.org/3/howto/sorting.html