python - Quicksort a list containing lists using python

Question

If I have a list defined as such:

myresults = [
    [1,"A",2],
    [2,"Z",1],
    [3,"J",0]
    ]

and I need to sort the list. I know I can use the sorted() function with a key function lambda=x:x[i] where i is the position to sort in a list. So this should work:

print sorted(myresults, key=lambda x:x[1])

and give back a list sorted on the 2nd column in the sub list.

How would you adapt a quicksort algorithm to handle a multi-dimensional list?

Answer 1

快速而肮脏的解决方案。如果您的快速排序如下所示：

def qsort(lst):
    if len(lst) == 0:
        return []
    else:
        pivot = lst[0]
        lesser = qsort([x for x in lst[1:] if x < pivot])
        greater = qsort([x for x in lst[1:] if x >= pivot])
        return lesser + [pivot] + greater

您可以只使用索引变量按所需维度排序：

def qsort_index(lst, index):
    if len(lst) == 0:
        return []
    else:
        pivot = lst[0]
        lesser = qsort_index([x for x in lst[1:] if x[index] < pivot[index]], index)
        greater = qsort_index([x for x in lst[1:] if x[index] >= pivot[index]], index)
        return lesser + [pivot] + greater



>>> qsort_index(myresults, 0)
[[1, 'A', 2], [2, 'Z', 1], [3, 'J', 0]]
>>> qsort_index(myresults, 1)
[[1, 'A', 2], [3, 'J', 0], [2, 'Z', 1]]
>>> qsort_index(myresults, 2)
[[3, 'J', 0], [2, 'Z', 1], [1, 'A', 2]]

这种实现远非最佳，但我认为你明白了。

Answer 2

您可以使用 Python 的operator模块。

import operator
sorted(myresults, key=operator.itemgetter(0))
[[1, 'A', 2], [2, 'Z', 1], [3, 'J', 0]]
sorted(myresults, key=operator.itemgetter(1))
[[1, 'A', 2], [3, 'J', 0], [2, 'Z', 1]]

Answer 3

您可以通过这种方式实现：

import operator
list.sort(key=operator.itemgetter(*args))

这也可以..

import operator
sorted(list, key=operator.itemgetter(1))