Python中快速排序小列表的方法

Question

我有很多非常小的列表需要尽快排序。通常这些列表里只有2到3个值，而内置的排序方法似乎开销太大。在这种情况下，使用简单的冒泡排序可以吗？

举个例子，我想排序：

[1, 5]
[4, 2]
[3, 7]
...

变成：

[1, 5]
[2, 4]
[3, 7]
...

现在我正在做类似这样的事情：

def do_something( ilist ):
    ilist = sorted(ilist, reverse = True);
    return ilist;

for i in range(1000000000):
    do_something( [random_num,random_num ] );

谢谢。

Answer 1

使用 sorted() 函数是非常高效的：

>>> list_of_lists = [[1, 5], [4, 2], [3, 7]]
>>> sorted_lol = [sorted(sub_list) for sub_list in list_of_lists]
>>> sorted_lol
[[1, 5], [2, 4], [3, 7]]

Answer 2

values = [{1, 5},{4, 2},{3, 7}]
print(sorted(values))

[set([1, 5]), set([2, 4]), set([3, 7])]

结果：

Answer 3

如果只有两个元素：

f = lambda x: x if x[0] < x[1] else [x[1],x[0]]

那么

x = [5,4]
f(x)

这会返回 '[4,5]'

x = [4,5]
f(x)

也会返回 [4,5]

不过如果元素超过两个，这种方法就不管用了，虽然你可以单独处理三个元素的情况。这种方法只是进行了一次比较和交换，而不是调用完整的排序函数。

Answer 4

是的。

如果这个列表里的每个子列表都有两个元素，那么用 > 这个符号来比较会比用 sorted 函数快。

[(i[1], i[0]) if i[0]>i[1] else i for i in lst]

时间：

lst = [(0, 9),
       (1, 8),
       (2, 7),
       (3, 6),
       (4, 5),
       (5, 4),
       (6, 3),
       (7, 2),
       (8, 1),
       (9, 0)]

%timeit [(i[1], i[0]) if i[0]>i[1] else i for i in lst]
1000000 loops, best of 3: 1.96 us per loop

%timeit [sorted(i) for i in lst]
100000 loops, best of 3: 5.87 us per loop

在你的情况下，你提到你的列表有2个或3个元素。所以你的排序函数看起来是这样的。

def sort_few(lst):
    if len(lst)==2:
        if lst[0] > lst[1]:
            return (lst[1], lst[0])
        else:
            return lst
    else:
        if lst[0] > lst[1]:
            if lst[1] > lst[2]:
                return (lst[2], lst[1], lst[0])
            else:
                return (lst[1], lst[2], lst[0])
        elif lst[1] > lst[2]:
            if lst[2] > lst[0]:
                return (lst[0], lst[2], lst[1])
            else:
                return (lst[2], lst[0], lst[1])
        elif lst[2] > lst[0]:
            if lst[0] > lst[1]:
                return (lst[1], lst[0], lst[2])
            else:
                return lst

时间：

lst = [(1, 2, 3),
       (1, 3, 2),
       (2, 1, 3),
       (2, 3, 1),
       (3, 1, 2),
       (3, 2, 1),
       (1, 2, 3),
       (1, 3, 2),
       (2, 1, 3),
       (2, 3, 1),
       (3, 1, 2),
       (3, 2, 1)]


%timeit [sort_few(i) for i in lst]
100000 loops, best of 3: 6.3 us per loop

%timeit [sorted(i) for i in lst]
100000 loops, best of 3: 7.32 us per loop

所以如果列表里有2个或3个元素，使用 sort_few 会比用 sorted 更快。