作为一个对编程相当陌生的人，我正在尝试在Python中实现快速排序。但是，我正在尝试以某种方式实现它，这似乎不是最常见的一种。我正在使用CS50在此视频中解释的技术：https://www.youtube.com/watch?v=aQiWF4E8flQ
此版本的算法在数组的末尾选择一个透视，在开头放置一堵"墙"并开始迭代列表。当它找到比枢轴小的项时，它会将该项与墙右侧的项交换，并将墙向右移动一个位置。将所有项目与枢轴进行比较时，它会将枢轴放在墙上，墙向右移动一个位置。这一直持续到墙在阵列的末尾。
到目前为止，我已经提出了这个：
def quicksort(alist):
quicksort_helper(alist)
print alist
def quicksort_helper(alist):
wall = 0
while wall < (len(alist) - 1):
pivot = len(alist) - 1
for current in range(wall, pivot):
if alist[current] < alist[pivot]:
alist[current], alist[wall] = alist[wall], alist[current]
wall = wall + 1
alist[wall], alist[pivot] = alist[pivot], alist[wall]
wall = wall + 1
当我尝试运行该程序时，墙壁和透视的数组索引一直遇到问题，因为这是我收到的错误消息：
IndexError: list index out of range
我已经尝试了很多索引，但我似乎无法弄清楚。
快速排序的工作原理如下： 首先对数组进行分区，以便有三个子数组： 左边的数组包含所有小于 pivod 的元素，排名不分先后。中间的"数组"只是一个元素，即枢轴*。右侧数组包含大于或等于透视表的所有元素。
现在已知枢轴处于其正确位置。然后，您必须对左右子数组进行排序。
分区是在墙的帮助下完成的。枢轴的位置是固定的;它始终是最右边的元素。然后，您将每个元素与枢轴对齐，如果它较小，则将其移动到墙的左侧。您必须将墙向右移动，以便为元素腾出空间。
查看所有元素后，您拥有三个子数组，但顺序错误：左、右、枢轴。（墙是左右子阵列之间的屏障。为了使其按正确的顺序排列，请使用枢轴交换墙右侧的元素，但不要移动墙。这只需要在分区循环之后执行一次。（请注意，如果枢轴恰好是最大的元素，则可以将枢轴与自身交换，这没关系，如果浪费的话。
您的算法使用 0 和数组的第 ength 作为绑定。这适用于整个阵列。当您要对子数组进行排序时，您必须调整这些边界。因此，最好将边界传递给快速排序帮助程序，以便可以递归。（当索引从零开始时，将下限包含和上限设置为排除是可行的，就像索引len(a)超出a的有效索引范围一样。
这是一个可行的解决方案：
def quicksort(alist):
quicksort_helper(alist, 0, len(alist))
def quicksort_helper(alist, l, r):
if l < r:
wall = l
pivot = r - 1
for current in range(wall, pivot):
if alist[current] < alist[pivot]:
alist[current], alist[wall] = alist[wall], alist[current]
wall = wall + 1
alist[wall], alist[pivot] = alist[pivot], alist[wall]
quicksort_helper(alist, l, wall)
quicksort_helper(alist, wall + 1, r)
*）有一个三向快速排序，它将所有相同值的透视组合在一起，以改善快速排序对只有几个唯一元素的数组的糟糕性能。
alist[wall], alist[pivot] = alist[pivot], alist[wall]在某些情况下，在值递增并导致触发IndexError len(alist)后执行wall。
您可以使用pdb来调试代码，在函数中添加行import pdb;pdb.set_trace()以跟踪变量值。