按不同值快速排序

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

您可以调整您的枢轴值和比较函数来执行您想要的任何逻辑，但是，在大多数情况下，您希望执行“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]))

按不同值快速排序

QuickSort by different values

python-3.x

algorithm

sorting

quicksort