快速排序 python 实施

Question

我正在尝试编写一个快速排序的实现，其中主元素是伪随机的。我在网上查看了各种帖子，很多都是关于 SO 的，但我仍然遇到问题。这是我的代码：

def quickSort(lst, a, b):
    if a < b:
        pivot = partition(lst, a, b)
        quickSort(lst, a, pivot-1)
        quickSort(lst, pivot+1, b)
    return lst



def partition(lst, a ,b):
    pivot = random.randint(a,b)
    for i in range(a,b):
        if lst[i] < lst[b]:
            lst[i],lst[pivot] = lst[pivot],lst[i]
            pivot += 1
    lst[pivot],lst[b] = lst[b],lst[pivot]
    return pivot

此代码实际上与为回答此问题而提供的代码相同：quick sort python recursion 但我没有使用 start 元素作为基准，而是使用随机。我不断收到此错误：

 in partition
    lst[pivot],lst[b] = lst[b],lst[pivot]
IndexError: list index out of range

我已经查过了，我认为这意味着我正在尝试引用列表中不存在或超出列表范围的元素。为什么会这样？

我也尝试过使用此 link 中实现的快速排序样式，但我遇到了同样的错误：Quicksort implementation in Python

Answer 1

我认为您误解了 partition 中的 pivot 值的含义。它不是被分区的元素的索引。无论如何，直到函数结束。实际主元值为 lst[b]，即被分区列表部分中的最后一个元素。该值被移动到函数倒数第二行的 pivot 位置。

pivot 值只是 "high" 值开始的索引。为 pivot 选择一个随机初始值会破坏算法，因为它可能会从列表末尾递增（考虑如果 random.randint(a, b) returns b 会发生什么）。

如果您想要一个随机值进行分区，请选择一个随机索引并在运行算法的其余部分正常之前将其值与 lst[b] 交换（使用 pivot索引从 a 开始):

def partition(lst, a ,b):
    random_index = random.randint(a,b)  # pick random index, its value will be our pivot val
    lst[b], lst[random_index] = lst[random_index], lst[b]   # swap the value with lst[b]

    pivot = a        # run the rest of the partition code as it was in the original version
    for i in range(a,b):
        if lst[i] < lst[b]:
            lst[i],lst[pivot] = lst[pivot],lst[i]
            pivot += 1
    lst[pivot],lst[b] = lst[b],lst[pivot]
    return pivot

快速排序 python 实施

Quicksort python implementation

python

quicksort