实现快速排序 CS50 样式时出现 IndexError
IndexError when implementing quicksort CS50 style
作为编程新手，我正在尝试在 Python 中实现快速排序。但是，我正在尝试以一种似乎不是最常见的方式来实现它。我正在使用 CS50 在此视频中解释的技术：https://www.youtube.com/watch?v=aQiWF4E8flQ
这个版本的算法在数组的末尾选择一个主元，在开头放置一个 "wall" 并开始迭代列表。当它找到一个小于枢轴的项目时，它将那个项目与墙右侧的项目交换，并将墙向右移动一个位置。当所有项目都与枢轴进行比较时，它将枢轴放在墙上，并且墙壁向右移动一个位置。这一直持续到墙位于阵列的末端。
到目前为止，我想出了这个：
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
我已经尝试了很多索引，但我似乎无法弄明白。
在某些情况下，alist[wall], alist[pivot] = alist[pivot], alist[wall] 行在 wall 值递增后执行并导致 len(alist) 触发 IndexError。
您可以使用 pdb 调试代码，在函数中添加行 import pdb;pdb.set_trace() 以跟踪变量值。
Quicksort 的工作原理如下：首先将数组划分为三个子数组： 左侧数组包含所有小于 pivod 的元素，没有顺序。中间的"array"只是一个元素，pivot*。右数组包含大于或等于主元的所有元素。
现在已知枢轴处于正确位置。然后，您必须对左右子数组进行排序。
分区是借助墙完成的。枢轴的位置是固定的；它总是最右边的元素。然后将每个元素与枢轴进行比较，如果它较小，则将其移动到墙的左侧。您必须将墙向右移动以便为元素腾出空间。
查看完所有元素后，您得到了三个子数组，但顺序错误：左、右、主元。 （墙是左右子数组之间的屏障。）为了将其置于正确的顺序，将元素与枢轴交换到墙的右侧，但不要移动墙。这只需在分区循环之后执行一次。 （请注意，如果枢轴恰好是最大的元素，则将枢轴与其自身交换，这没关系，如果浪费的话。）
您的算法使用 0 和数组的长度作为绑定。这适用于整个阵列。当你想对子数组进行排序时，你必须调整这些边界。因此，将边界传递给快速排序助手是个好主意，这样您就可以递归。 （下限包含，上限不包含是总结，就像索引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)
*) 有一个三向快速排序，它将所有相同值的枢轴组合在一起，以改善快速排序对只有少数唯一元素的数组的不良性能。
作为编程新手，我正在尝试在 Python 中实现快速排序。但是，我正在尝试以一种似乎不是最常见的方式来实现它。我正在使用 CS50 在此视频中解释的技术：https://www.youtube.com/watch?v=aQiWF4E8flQ
这个版本的算法在数组的末尾选择一个主元，在开头放置一个 "wall" 并开始迭代列表。当它找到一个小于枢轴的项目时，它将那个项目与墙右侧的项目交换，并将墙向右移动一个位置。当所有项目都与枢轴进行比较时，它将枢轴放在墙上，并且墙壁向右移动一个位置。这一直持续到墙位于阵列的末端。
到目前为止，我想出了这个：
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
我已经尝试了很多索引，但我似乎无法弄明白。
在某些情况下，alist[wall], alist[pivot] = alist[pivot], alist[wall] 行在 wall 值递增后执行并导致 len(alist) 触发 IndexError。
您可以使用 pdb 调试代码，在函数中添加行 import pdb;pdb.set_trace() 以跟踪变量值。
Quicksort 的工作原理如下：首先将数组划分为三个子数组： 左侧数组包含所有小于 pivod 的元素，没有顺序。中间的"array"只是一个元素，pivot*。右数组包含大于或等于主元的所有元素。
现在已知枢轴处于正确位置。然后，您必须对左右子数组进行排序。
分区是借助墙完成的。枢轴的位置是固定的；它总是最右边的元素。然后将每个元素与枢轴进行比较，如果它较小，则将其移动到墙的左侧。您必须将墙向右移动以便为元素腾出空间。
查看完所有元素后，您得到了三个子数组，但顺序错误：左、右、主元。 （墙是左右子数组之间的屏障。）为了将其置于正确的顺序，将元素与枢轴交换到墙的右侧，但不要移动墙。这只需在分区循环之后执行一次。 （请注意，如果枢轴恰好是最大的元素，则将枢轴与其自身交换，这没关系，如果浪费的话。）
您的算法使用 0 和数组的长度作为绑定。这适用于整个阵列。当你想对子数组进行排序时，你必须调整这些边界。因此，将边界传递给快速排序助手是个好主意，这样您就可以递归。 （下限包含，上限不包含是总结，就像索引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)
*) 有一个三向快速排序，它将所有相同值的枢轴组合在一起，以改善快速排序对只有少数唯一元素的数组的不良性能。