1

我需要编写一个函数来对只有 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
4

7 回答 7

3

这会做到的。它可能不是最优雅的，但它简单易行：

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

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

于 2013-08-05T05:41:55.533 回答
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。

于 2013-08-05T06:01:21.293 回答
1

我忍不住想用 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]
于 2013-08-05T06:23:50.717 回答
0 
def sort(arr):
    leftside = []
    rightside = []
    for elem in arr:
        leftside.append(elem) if elem == 0 else rightside.append(elem)

    return leftside + rightside


mylist = [0, 1, 0, 1, 0]

print sort(mylist)

现在，如果它不只是 1 和 0，那么您的代码将开始看起来像快速排序，具有左侧和右侧的递归排序。但由于它只有 1 和 0，我认为它看起来像那样。

于 2013-08-05T07:50:24.423 回答
0

我认为你可以这样做，它是线性的并且就地排序。基本上它是两个指针，一个从头开始显示 0 的结束位置，另一个从末尾开始显示 1 的开始位置。

def mysort(a, i=None, j=None):
    if not i: i = 0
    if not j: j = len(a) - 1
    if i >= j: return
    if a[i] == 1:
        a[j], a[i] = 1, a[j]
        mysort(a, i, j - 1)
    else:
        mysort(a, i + 1, j)

这是跟踪：

>>> a = [1, 1, 0, 1, 0]
>>> mysort(a)
 i           j
[1, 1, 0, 1, 0]

 i        j 
[0, 1, 0, 1, 1]

    i     j
[0, 1, 0, 1, 1]

    i  j
[0, 1, 0, 1, 1]

       i
[0, 0, 1, 1, 1]
于 2013-08-05T05:59:32.723 回答
0

这不是特别快，但它是一行：

sorted_list = [i for i in original_list if not i] + [i for i in original_list if i]
于 2013-08-05T06:07:27.120 回答
0

这是一个简单的代码，比本页中的任何其他代码都容易，这一行是 line=map(int,input("").split()) 将输入放在一行中并拆分为一个列表并将所有元素映射到转换成整数

list=sorted(line) this 对整数元素列表进行排序

n=input() #size of an array
line=map(int,input("").split()) #elements of the list
list=sorted(line) #sorting the list
print (*list) #To print elements with space use *list eg:- 0 0 1 1 1 1
于 2018-08-27T16:44:10.707 回答