对只包含0和1的列表进行高效排序，而不使用任何内置的python排序函数？

Question

对元素仅为0&；1的列表排序最有效的方法是什么。O（n）或更小

Answer 1

有许多不同的通用排序算法可以使用。但是，在这种情况下，最重要的考虑是所有要排序的元素都属于集合（0,1）。在

正如其他贡献者所回答的，有一个微不足道的实现。在

def radix_sort(a):
    slist = [[],[]]
    for elem in a:
        slist[elem].append(elem)
    return slist[0] + slist[1]

print radix_sort([0,0,1,0,1,1,0])

必须注意，这是Radix sort的一个特定实现。如果要排序的列表元素属于一个已定义的有限集，则可以很容易地扩展这一点。在

^{pr2}$

没有sort()或sorted()或count()函数。O（n）

Answer 2

这个是O(n)（你不能少得到）：

old = [0,0,1,0,1,1,0]
zeroes = old.count(0) #you gotta count them somehow!
new = [0]*zeroes + [1]*(len(old) - zeroes)

由于没有Python循环，这可能是在纯Python中可以获得的更快。。。在

Answer 3

>>> lst = [0,0,1,0,1,1,0]
>>> l, s = len(lst), sum(lst)
>>> result = [0] * (l - s) + [1] * s
>>> result
[0, 0, 0, 0, 1, 1, 1]