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

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

このようにできると思います。線形で、その場でソートされます。基本的には 2 つのポインターです。1 つは最初から始まり、0 の終わりを示し、もう 1 つは終わりから始まり、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

これは特に高速ではありませんが、1 行です。

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 に答える