在Python中，如何按元素频率排序列表

Question

我有一个元素列表：[ 3, 3, 6, 6, 6, 5, 5, 8 ]，我想按照元素出现的频率来排序，最终得到这个结果：[ 6, 6, 6, 3, 3, 5, 5, 8 ]。如果有几个元素的出现频率相同，那就按照它们的数值来排序。你能找到比这个更简短的方法吗？

import collections
from operator import itemgetter, attrgetter

def freq_sort(arr):
    counter=collections.Counter(arr)
    com = sorted(counter.most_common(), key=itemgetter(1,0), reverse=True)
    com = map(lambda x: [x[0]] * x[1], com)
    return [item for sublist in com for item in sublist]

Answer 1

进行两次排序通常比使用一个额外的lambda函数要快。这是因为Python的排序是稳定的。

>>> from collections import Counter
>>> L = [ 3, 3, 6, 6, 6, 5, 5, 8 ]
>>> c = Counter(L)
>>> sorted(sorted(L), key=c.get, reverse=True)
[6, 6, 6, 3, 3, 5, 5, 8]

第二次排序会很快，因为数据现在已经部分排序了，而timsort在处理这种情况时表现得特别好。

Answer 2

这段代码的行数比较少，首先是按照数量进行排序，然后再按照数值进行排序：

import collections
arr = [ 3, 3, 6, 6, 6, 5, 5, 8 ]
counter = collections.Counter(arr)
sorted( arr, key=lambda x: (counter[x], x), reverse=True )

Answer 3

collections.Counter的most_common()方法几乎能满足你的需求。它会返回一个按出现频率排序的值和频率的配对。但是，你还希望列表按值排序；这个方法并不能保证这一点（说明书上说，当频率相同时，值的顺序是随意的）。所以我们需要把它传给sorted()函数。

下面是代码：

from collections import Counter

l = [ 3, 3, 6, 6, 6, 5, 5, 8 ]
c = Counter(l)
sc = sorted(c.most_common(), key=lambda x: (-x[1], x[0])) # sorting happens here
sl = [([v] * n) for (v, n) in sc]
ss = sum(sl, [])
print(ss)

这个方法有一个优点，就是它的运行时间只有O(m log m)，其中m是列表中不同值的数量。而其他方法的运行时间是O(n log n)，其中n是列表的长度，这个长度总是大于或等于不同值的数量。你基本上会使用桶排序算法。

Answer 4

试试这个

>>> old_list = [ 3, 3, 6, 6, 6, 5, 5, 8 ]
new_list = sorted(old_list, key = old_list.count, reverse=True)
>>> new_list
[6, 6, 6, 3, 3, 5, 5, 8]