对奇数和偶数进行排序

Question

我有一串数字，我想把它们排序，让奇数在前面，偶数在后面。而且我想用递归的方法来实现，因为用循环来做其实不难。不过我遇到了一个错误，提示说“超过了最大递归深度”。这是我的代码：

def sep(l,i,j):
    def swap(l,i,j):
        (l[i],l[j]) = (l[j],l[i])
    n = len(l)
    i = 0
    j = n-1

    if l[i]%2 == 0:
        swap(l,i,j)
        j-=1
        return l 

   else:
        return  sep(l,i+1,j)
l =[5,13,12,4,6,9]
i =0
j =len(l)-1
print(sep(l,i,j))

Answer 1

如果不想使用自己的函数或者递归的话，sorted()这个函数就很合适。

arr = [5,13,12,4,6,9]
arr = sorted(arr, key=lambda x: (x % 2 == 0, x))
print(output)

输出结果

[5, 9, 13, 4, 6, 12]

Answer 2

这段代码运行得很正常。至于为什么你的代码不行，我觉得@AMacK和@JohnBarca的评论会对你有帮助：

lst = [5,13,12,4,6,9]

def sep(l,i):
    if len(l)-i < 2: return
    for j in range(len(l)-i):
        if l[i]%2==0 and l[i+j]%2==1:
            l[i],l[i+j] = l[i+j],l[i]
    sep(l,i+1)

sep(lst,0)

>>> print lst
[5, 13, 9, 4, 6, 12]

Answer 3

def rec(lst, start, end):
    if start == end:
        return lst
    elif lst[start] % 2 == 0 and lst[end] % 2 == 1:
        lst[start], lst[end] = lst[end], lst[start]
        return rec(lst, start+1, end-1)
    elif lst[start] % 2 == 0:
        return rec(lst, start, end-1)
    else:
        return rec(lst, start+1, end)



def rec_sort(lst):
    return rec(lst, 0, len(lst)-1)


print rec_sort([1,2,3,4,5,6])

输出：

[1, 5, 3, 4, 2, 6]

Answer 4

# called with list, 0, len(list)-1
def sep(lst, first, last):
    def swap(l, x, y):
        l[x], l[y] = l[y], l[x]
    # basecase: done searching list
    if first == last or first > last:
        return lst
    # even left: continue ignoring the first
    if lst[first] % 2 == 0:
        return sep(lst, first+1, last)
    # odd left: continue ignoring the last
    if lst[last] % 2 == 1:
        return sep(lst, first, last-1)
    swap(lst, first, last)
    return sep(lst, first+1, last-1)
l = [5,13,12,4,6,9]
print sep(l, 0, len(l)-1)

是的，你的问题在评论里提到了。如果你在函数内部一直设置 i 和 j，那么每次需要递归调用 sep 的时候，i 和 j 就会一直重复设置，i 会变成 0，j 会变成整个列表长度减去 1。

要进行递归调用，你不需要每次都设置 i 和 j，而是需要在每次调用时让它们分别加一和减一。这样你才能知道递归什么时候结束。当你遍历到列表的某个点，两个指针互相指向，或者已经交叉过去时，就说明结束了。

结束时你不应该返回 1，而是应该返回整个列表。而且在交换 j 的值之后，要记得把 j 减一。