使用选择排序对列表排序

Question

我有一个包含多个列表的列表，我想根据每个子列表的第一个元素进行升序排序。如果这些子列表的第一个元素相同，那么就要根据第二个元素进行排序。

到目前为止，我只能根据第一个元素进行排序。我使用了插入排序的方法来进行排序。如果第一个元素相同，怎么才能根据第二个元素进行排序呢？

def sort_list ():
    # An example of the list to be sorted
    original_list = [['Glenn', 'Stevens'],
                    ['Phil', 'Wayne'],
                    ['Peter', 'Martin'],
                    ['Phil', 'Turville'],
                    ['Chris', 'Turville']]

    sorted_list = list(original_list)

    for index in range(1, len(sorted_list)):           
        pos = index                                 
        while pos > 0 and sorted_list[pos - 1][0] > sorted_list[pos][0]:    
            sorted_list[pos-1], sorted_list[pos] = sorted_list[pos], sorted_list[pos-1]
            pos -= 1                            

    return sorted_list

Answer 1

列表比较已经按照你想要的方式工作了，这种方式叫做字典序：首先比较第一个元素，如果相等，就比较第二个及后面的元素。

这意味着你可以用一行代码来排序你的列表：

original_list.sort()

如果你需要自己实现排序功能，应该以一种通用的方式来做，传入一个键函数（就像内置的 sorted 函数那样）。

def insertion_sort(xs, key=(lambda x: x)):
    result = list(xs)
    for i in xrange(len(result)):
        for pos in xrange(i, 0, -1):
            if key(result[pos-1]) <= key(result[pos]):
                break
            result[pos-1], result[pos] = result[pos], result[pos-1]
    return result

这样你就可以根据每个子列表的第一个元素来排序：

print insertion_sort(xs, key=(lambda x: x[0]))

或者按照字典序来排序：

print insertion_sort(xs)

Answer 2

如果你想用自己的函数来进行排序，是完全可以的。

如果你想在第一个元素相等的情况下检查第二个元素，只需写

   (sorted_list[pos - 1][0] > sorted_list[pos][0] 
or (sorted_list[pos - 1][0] == sorted_list[pos][0] 
    and sorted_list[pos - 1][1] > sorted_list[pos][1]))

而不是

sorted_list[pos - 1][0] > sorted_list[pos][0]

其实你可以写得更简洁一些：

sorted_list[pos - 1] > sorted_list[pos]

这正是你需要的。

当Python比较列表时，它是从第一个元素开始逐个比较的：[0]：

>>> a=[1,2]
>>> b=[1,1]
>>> a<b
False
>>> a=[1,2]
>>> b=[1,3]
>>> a<b
True
>>> a=[1,2]
>>> b=[2,1]
>>> a<b
True