在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]

- mnowotka

---

适合发布在codereview.stackexchange网站上。 - Games Brainiac

定义“更短”。Darth Kotik提出的答案在字符方面更短，但是对于列表中的每个唯一元素它会多执行一个循环。值得注意的是，如果在可变元素的列表上使用你给出的解决方案会带来问题。 - Dunes

Answer 1

试试这个

>>> 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]

- Darth Kotik

---

当计数相等时，这种方法不会按值进行排序。而且，将list.count作为键函数并不是很高效（会使排序变为O(N*N)）。 - John La Rooy

你能进行一些基准测试来展示执行时间与所讨论的解决方案相比如何吗？ - mnowotka

如果old_list的长度可观，你可能想要记忆化old_list.count。 - jacg

Answer 2

collections.Counter方法most_common()几乎可以满足你的需求。它按频率排序返回(value, frequency)对。你还需要按值排序列表；该方法不能保证这一点（规范说当频率相同时，值的顺序是任意的）。因此我们需要将其传递给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是l中不同值的数量。而其他方法将需要O(n log n)的时间运行，其中n为l的长度，始终大于或等于不同值的数量。您将基本上使用桶排序算法。

- haael

Answer 3

进行两次排序通常比使用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擅长的地方。

- John La Rooy

Answer 4

这段代码行数较短，首先按数量排序，然后按值排序：

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 )

- pm007

---

应该使用(counter[x], -x)来获得正确的顺序。 - John La Rooy