第二个元素作为快速排序中的枢轴

Question

我有一个涉及快速排序算法的作业。我从不同的文本和网站（如 GeeksforGeeks、FCC、JavaPoint 等）多次阅读过它。我了解算法，也了解示例代码。

我面临的问题是讲师要求枢轴是第二个元素，

arr[1]

。

这是我编写的用于分区的代码：

arr = [34, 8, 3, 4, 5, 67, 43]

pivot = arr[1]
j = 0
for i in range(len(arr)):
    if arr[i] >= pivot:
        j = i
    if arr[i] < pivot and i > 1:
        arr[i], arr[j] = arr[j], arr[i]

print(arr)

[What I got]: [34, 8, 3, 4, 5, 67, 43]

[Expected}: [4, 3, 5, 8, 67, 34, 43]

我知道该代码块应该包装在分区函数中，并且我将递归地对左右部分进行排序。

那么，有人可以帮我调查一下吗？

Answer 1

看起来您尝试实现 Lomuto 分区方案，但它存在一些问题：

1. j = i

   不对。它将

   j

   设置为您发现的不小于主元的“最新”条目。但因此您可能会跳过同样处于这种情况且尚未交换的先前条目。因此，前一个分区现在永远分配给左侧分区，而它最终应该位于右侧分区。相反，j应该指向您发现的不小于主元的第一个

   条目，或者换句话说，它应该标记右侧分区的开始，因此应该仅以步长1递增。

   循环结束后，您的代码无法确保枢轴值放置在两个结果分区之间。 Lomuto 分区方案执行此操作，以便调用者可以从将成为递归调用主题的两个分区中排除该索引。

2. 这是使用 Lomuto 分区方案的更正版本：

def partition(arr, lo, hi):
    pivot = arr[lo + 1]  # The second value in the current partition
    # Swap the pivot out of the way (to the far right)
    arr[hi], arr[lo + 1] = pivot, arr[hi]
    for i in range(lo, hi):  # Iterate the range, excluding the pivot
        if arr[i] <= pivot: 
            arr[i], arr[lo] = arr[lo], arr[i]
            lo += 1  # Increase the index where the righthand partition starts
    # Move the pivot value (from the right) to the correct pivot index
    arr[hi], arr[lo] = arr[lo], arr[hi]
    return lo  # Return the pivot index

致电：

arr = [34, 8, 3, 4, 5, 67, 43]
partition(arr, 0, len(arr) - 1)