对整数列表排序的递归函数

Question

我想定义一个递归函数，它可以对任何整数列表进行排序：

def sort_l(l):
    if l==[]:
        return []
    else:
        if len(l)==1:
            return [l[-1]]
        elif l[0]<l[1]:
            return [l[0]]+sort_l(l[1:])
        else:
            return sort_l(l[1:])+[l[0]]

在列表[3、1、2、4、7、5、6、9、8]上调用此函数应给出：

[1,2,3,4,5,6,7,8,9]

但我得到：

print(sort_l([3, 1, 2,4,7,5,6,9,8]))--> [1, 2, 4, 5, 6, 8, 9, 7, 3]

请帮助我解决问题，实际代码将不胜感激。谢谢！

Answer 1

def quicksort(lst):
    "Quicksort over a list-like sequence"
    if len(lst) == 0:
        return lst
    pivot = lst[0]
    pivots = [x for x in lst if x == pivot]
    small = quicksort([x for x in lst if x < pivot])
    large = quicksort([x for x in lst if x > pivot])
    return small + pivots + large

以上是一个更可读的递归实现的快速排序算法。上面这段代码来自O'REILLY用python编写的函数式编程 将产生上述功能。

list=[9,8,7,6,5,4]
quicksort(list)
>>[4,5,6,7,8,9]

Answer 2

quick sort是递归的，易于在Python中实现：

def quick_sort(l):
    if len(l) <= 1:
        return l
    else:
        return quick_sort([e for e in l[1:] if e <= l[0]]) + [l[0]] +\
            quick_sort([e for e in l[1:] if e > l[0]])

将给予：

>>> quick_sort([3, 1, 2, 4, 7, 5, 6, 9, 8])
[1, 2, 3, 4, 5, 6, 7, 8, 9]

Answer 3

为此，您需要使用合并排序。本质上，在合并排序中，您递归地将列表分成两半，直到只有一个元素，然后按照正确的顺序将其备份。merge sort on复杂度为O(n log(n))，是一种非常稳定的排序方法。

下面是一些很好的深度解释和合并排序的视觉效果：

• https://www.youtube.com/watch?v=vxENKlcs2Tw
• http://www.princeton.edu/~achaney/tmve/wiki100k/docs/Merge_sort.html