使用递归对只包含0和1的列表进行排序

Question

我需要编写一个函数来对仅包含1和0的列表进行排序，并且需要使用递归。我写了一个不需要递归就能排序的函数(一种修改过的计数排序，增加了一些限制，使它只接受1和0)。有没有办法使用递归重写我的解决方案？或者使用递归的问题的任何解决方案(可能是修改后的快速排序)？

def counting_sort(array):
   """sorting only ones and zeros"""
   count = [0] * 2               

   for a in array:
    count[a] += 1            
   i = 0
   for a in range(2):            
     for x in range(count[a]): 
        array[i] = a
        i += 1
   return array 

Answer 1

这样就可以了。它可能不是最优雅的，但它很简单：

def binSort(array):
    if len(array) == 0:
        return []
    if array[0] == 0:
        return [0] + binSort(array[1:])
    return binSort(array[1:]) + [1]

它查看列表中的第一个元素，将0放在开头，将1放在末尾，然后移动到列表的其余部分。如果你有问题，我很乐意回答。

Answer 2

这在O(n)时间内按原地排序：

def sort(list, fromIndex, toIndex):
    if fromIndex == toIndex:
        return list
    if list[fromIndex] == 0:
        return sort(list, fromIndex + 1, toIndex)
    else:
        list[fromIndex] = list[toIndex]
        list[toIndex] = 1
        return sort(list, fromIndex, toIndex - 1)

unsortedList = [0, 1, 1, 1, 0, 1, 0, 1, 1, 0, 0, 0, 1]
print sort(unsortedList, 0, len(unsortedList) - 1)

输出为：

[0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1]

编辑：将最小和最大变量名称更改为fromIndex和toIndex。

Answer 3

我忍不住想用Python迭代器fu尝试一下。下面的代码是递归的，并生成一个惰性序列：

from itertools import chain

def zero(): yield 0
def one(): yield 1

def sort01(items):
    if not callable(getattr(items, 'next', None)):
        items = iter(items)
    try:
        if items.next() == 0:
            return chain(zero(), sort01(items))
        else:
            return chain(sort01(items), one())
    except StopIteration:
        return tuple()

以下是演示：

>>> print list(sort01([0, 1, 1, 0, 0, 0, 0, 1]))
>>> [0, 0, 0, 0, 0, 1, 1, 1]