按不同值快速排序

Question

你好我有一个这样的列表：

list_ = [["a", 1],
["b", 3],
["c", 2],
["d", 2]]

我想每隔一秒对它进行排序，并且我可以使用快速排序来做到这一点。

def partition(a, low, high):
i = low - 1
pivot = a[high][1]

for j in range(low, high):

if a[j][1] >= pivot:
i += 1
a[i], a[j] = a[j], a[i]
def quicksort_inplace(a, low=0, high=None):
if high is None:
high = len(a) - 1
if low < high:
p_idx = partition(a, low, high)
quicksort_inplace(a, low, p_idx - 1)
quicksort_inplace(a, p_idx + 1, high)

return a

问题。我知道如何一次对一个项目进行排序，但我不知道如何对列表进行排序，这样，如果有相同的项目，排序就会按字母顺序(按第一个项目(进行。

在：

[
["a", 1],
["b", 3],
["c", 2],
["d", 2]
]

输出：

[
["b", 3],
["d", 2]
["c", 2],
["a", 1],
]

Answer 1

您可以调整您的pivot值和比较函数来执行您想要的任何逻辑，但是，正如大多数情况下一样，您希望执行"lexographic"；顺序幸运的是，python已经通过列表和元组为您实现了这种逻辑，比较第一个元素，如果相等，则转到下一个，然后再确定哪个更大。

仅使用

pivot = a[high]
...
if a[j] < pivot:

会先比较字符串，然后比较数字。然而，你想要另一个顺序，最重要的是，你想要颠倒数字。

最简单的就是创建一个可以排序的key。

pivot = (-a[high][1], a[high][0]) # reversed number first, then ordinary letter.
...
if (-a[j][1], a[j][0]) < pivot:

当然，我们也可以在正常的排序例程中使用key

sorted(list_, key=lambda x: (-x[1], x[0]))
list_.sort(key=lambda x: (-x[1], x[0]))