WIKIPEDIA 在 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

它不会抛出错误或打印任何内容，因为没有运行任何内容的主程序。您缩进了应该是主程序的内容，因此它现在是 quicksort 函数的一部分。

此外，此代码会引发错误，因为您在发布的内容中留下了评论。我会清理代码并编辑您的帖子。

我更正了几个代码错误：

删除了 "enter code here" 文本，这导致了明显的编译错误。
更正了缩进，现在最后三行是您的主程序。
更正了主程序调用：quicksort 采用数组的边界（下标），但您传入的是数组元素本身。

这解决了您给定的问题。由于没有正确处理 return 值，您现在有无限递归。此外，您的主程序会破坏已排序的数组，因为 quicksort 不会 return 任何东西。最终的打印语句将给出 None 作为结果。

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

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

解决这些问题，您将接近解决方案。

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

你为什么returnA从函数？ Wikipedia 算法不会这样做，也没有必要：您已就地更改了列表。

由于您已经了解多重赋值，请注意有一种更简单的方法可以交换两个值：

a, b = b, a

这是否能让您解决当前的问题，足以让您回到想要的学习轨道？

WIKIPEDIA 在 python 中所说的快速排序算法

quicksort algorithm as WIKIPEDIA says in python

python

algorithm

wikipedia

quicksort