标准排序函数文献会告诉您排序通常(合并、快速)可以在 N log N 中完成。
例如，如果我有这个列表:[1,6,3,3,4,2]
会在NlogN时间内排序为:[1,2,3,3,4,6]
如果我有一个按第一个属性排序的列表，然后是第二个属性怎么办？
像这样:[(1,1),(6,3),(3,4),(3,1),(2,8)] 到这样: [(1,1),(2,8),(3,1),(3,4),(6,3)]
它的时间复杂度是多少？
我想出的是，如果所有第一个索引都相同，那么您只是再次执行 N log N，所以是一样的。如果有一堆不同的第一个索引，那么您正在重新排序一堆小集合。
最佳答案
合并排序(或快速排序)执行 O(N log N) 比较。它的时间复杂度是 O(N log N * time_to_compare_two_elements)。比较一对元素的时间复杂度是常数(如果比较两个元素的时间是常数)。因此，对数组进行排序的时间复杂度也是 O(N log N)。
关于algorithm - 先按 x1 排序，然后按 x2 排序的时间复杂度？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/28141063/