像维基百科在python中所说的那样，快速排序算法

Question

在维基百科中，有一个快速排序算法的伪代码：

所以我尝试在python中实现，但是它没有排序任何东西。

def partition(A,lo,hi):
    pivot = A[hi]
    i=lo
    #Swap
    for j in range(lo,len(A)-1):
        if (A[j] <= pivot):
            val=A[i]
            A[i]=A[j]
            A[j]=val
            i=i+1
        val=A[i]
        A[i]=A[hi]
        A[hi]=val
    return(A,i)

def quicksort(A,lo,hi):
     if (lo<hi):
        [A,p]=partition(A,lo,hi)
        quicksort(A,lo,p-1)
        quicksort(A,p+1,hi)

A=[5,3,2,6,8,9,1]
A=quicksort(A, 0, len(A)-1)
print(A)

它不会抛出错误，所以我不会在哪里出错。

更新:现在进入无限递归。

Answer 1

它不会抛出错误或打印任何东西，因为没有主程序来运行任何东西。您缩进了什么应该是主程序，所以现在它是快速排序函数的一部分。

另外，这段代码确实会抛出一个错误，因为您在发布的内容中留下了注释。我会清理代码并编辑你的帖子。

我纠正了几个代码错误：

1. 删除了“在这里输入代码”文本，这导致了一个明显的编译错误。
2. 修正缩进，使最后三行现在是你的主程序。
3. 更正了主程序调用：quicksort获取数组的边界(下标)，但是您传递的是数组元素本身。

解决了你的问题。由于没有正确处理返回值，您现在有无限递归。而且，您的主程序破坏排序数组，因为快速排序不返回任何内容。最后的打印语句将给出None作为其结果。

您还没有完全实现给定的算法。最重要的问题是for循环的上限。

• Python循环不包括结束值。给定的循环将运行j，通过通过len(A)-2的值lo，因此您将永远不会处理列表的最后一个值。
• 维基百科给出的上限是hi，而不是列表的末尾。

解决这些问题，你就能找到解决方案了。

此外，我强烈建议您坚持使用几个跟踪打印语句，这样您就可以看到程序是如何工作的。例如，作为每个函数的第一个语句，打印函数名和输入参数。

为什么你从函数中返回A？维基百科的算法并没有做到这一点，也没有必要:你修改了列表。

既然您已经了解了多个赋值，请注意有一种更简单的方法来交换两个值：

a, b = b, a

这能让你克服当前的问题，让你重新回到你想要的学习轨道上吗？