我不能从快速输出中得到输出

Question

我不会从下面的快速排序代码中得到输出：

def quick_sort(sequence):
    length = len(sequence)
    if length<=1:
        return sequence
    else:
        pivot = sequence.pop()
        item_greater = []
        item_lower = []
        for item in sequence:
            if item> pivot:
                item_greater.append(item)

            else:
                item_lower.append(item)
                print( quick_sort(item_lower) + [pivot]  + quick_sort(item_greater))

测试快速排序算法：

print(quick_sort([91,45,78,124,174,32,75,69,43,15,2,45,19,66]))

Answer 1

返回您的值，而不是打印出来：

def quick_sort(sequence):
    length = len(sequence)
    if length<=1:
        return sequence
    else: pivot = sequence.pop()
    item_greter = []
    item_lower = []
    for item in sequence:
        if item > pivot: item_greter.append(item)

        else:
            item_lower.append(item)
            return quick_sort(item_lower) + [pivot]  + quick_sort(item_greter)
            
print(quick_sort([91,45,78,124,174,32,75,69,43,15,2,45,19,66]))

Answer 2

这些是主要问题：

1. 您的函数不返回结果，因此您将从递归调用中获得None，然后+ [pivot]操作将引发一个错误。

1. 与前一点有关:当递归结果返回时，不应该打印它。只有当最终结果准备就绪时，才应该进行打印，即这是原调用方的一项任务(在主代码中)。

1. 递归调用不应该在填充两个分区的循环中进行。它应该在循环

之后进行。

没有问题，但"greter“的拼写”更大“

另外，您可以跳过第一个else，因为if块将以return结尾。

更正：

def quick_sort(sequence):
    length = len(sequence)
    if length <= 1:
        return sequence
    pivot = sequence.pop()
    item_greater = []
    item_lower = []
    for item in sequence:
        if item > pivot: 
            item_greater.append(item)
        else:
            item_lower.append(item)
    return quick_sort(item_lower) + [pivot]  + quick_sort(item_greater)


print(quick_sort([91,45,78,124,174,32,75,69,43,15,2,45,19,66]))

结束语

1. 这个函数破坏输入列表不是件好事。如果调用方有对该列表的引用，并在调用后对其进行检查，则它将缺少一个元素。这是由于在其上执行的第一个pop：

lst = 91,45,78,124,174,32,75,69,43,15,2,45,19,66打印(quick_sort(Lst))打印(Lst)#缺少最后一个元素，并且没有排序

1. 快速排序是一种就地排序算法，因此不需要创建新列表(item_greater和item_greater)。相反，这些分区应该通过交换输入列表中的值来形成。在这样的implementation.

中不应该有[] (新的空列表)或+ (列表连接)。

本地快速排序算法的正确版本随时可用.有许多可能的变体，取决于枢轴选择。在这个网站上也有几个关于这个主题的问答。例如，见：

• In-place QuickSort in Python
• inplace quick sort implementation
• How to implement quick sort when middle element is the pivot?
• Python Quicksort implementation