快速排序实现Python - 了解基本案例

Question

我一直在尝试通过使用左右指针方法在 Python 中自己实现快速排序来理解快速排序。我似乎无法让它工作并在线查看可视化，我无法理解快速排序在长度为 2 的列表上操作时如何工作。根据我读过的大多数资料，您应该选择一个枢轴和您的向左/向右移动时，左指针和右指针不应该包含该枢轴值。当列表的长度为 2 时，您选择一个枢轴并留下长度为 1 的列表，并且左/右立即相遇。快速排序如何对输入 [5,4] 进行排序？ 这是我写的Python代码：

def quicksort(arr, low, high):
  if low < high:
    pivot_index = partition(arr, low, high)
    quicksort(arr, low, pivot_index-1)
    quicksort(arr, pivot_index+1, high)

  return arr

def partition(arr, low, high):
  # select last element as pivot
  pivot_index = high
  pivot = arr[high]
  left_wall = low
  # exclude pivot from left/right searching
  right_wall = high-1

  # keep searching until next swap point found
  while left_wall < right_wall:
    # if left wall value is not greater than pivot, keep searching
    while arr[left_wall] <= pivot:
      left_wall += 1
    # if right wall value is not less than pivot, keep searching
    while arr[right_wall] >= pivot:
      right_wall -= 1
    if left_wall < right_wall:
      # perform swap
      temp_left_wall = arr[left_wall]
      arr[left_wall] = arr[right_wall]
      arr[right_wall] = temp_left_wall

  # swap pivot with right wall
  arr[pivot_index] = arr[right_wall]
  arr[right_wall] = pivot
  return right_wall


quicksort([5,4,3,2],0,3)

有人可以帮助我理解我对快速排序过程不理解的地方吗？

Answer 1

如果我们查看

quicksort

函数，我们会看到 Lomuto 方案的典型模式（Hoare 方案返回不一定具有主元值的索引）。

partition

函数的第一部分也遵循 Lomuto 方案。

但是在循环中你的逻辑

类似于

霍尔方案。这是在自找麻烦。 维基百科关于快速排序和霍尔分区方案警告：

相对于这个原始描述，实现通常会做出微小但重要的变化。 [...] 霍尔分区方案实现的正确性争论可能很微妙，而且很容易出错。

这里出了问题：

最内层循环中的索引很容易超出数组的范围。例如，如果我们给出 [3, 2, 1] 或 [1, 2, 3] 或 [1, 1, 1] 作为输入，我们得到：

IndexError：列表索引超出范围

Hoare 方案不存在这个问题，因为一旦找到等于主元的值，它就会退出内部循环

并且

因为可以确定主元值在当前窗口内至少出现一次。后者在您的实现中是不正确的，因为您从一开始就从窗口中排除了枢轴元素 - 这是 Lomuto 系统。以下是维基百科如何表示这些霍尔内循环：

    do i := i + 1 while A[i] < pivot
    do j := j - 1 while A[j] > pivot

另请注意，这些循环始终对相应索引至少应用一次更新。这很重要，因为执行交换后，两个索引仍然可能表示不满足内部循环条件（如果已更正）的值。这可能会导致无限循环。

如您所见，细节很重要...非常重要。

快速排序分区并不像乍一看那么简单。有几个陷阱。

我建议要么实现 Lomuto 方案，要么实现 Hoare 方案（不要混合它们！），并使用维基百科上提供的相应伪代码作为起点。