快速排序python实现

Question

我想写一个快速排序的实现，其中的枢轴元素是伪随机的。我在网上看过各种帖子，很多都是关于这个帖子的，但我仍然有问题。这里是我的代码：

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 

我已经看过那个了，我想这意味着我试图引用不存在或出名单的范围列表的元素。这是为什么发生？

我也用在这个环节上实现快速排序的风格尝试，我得到同样的错误：Quicksort implementation in Python

Answer 1

我想你已经在partition手段误解是什么pivot值。它不是被分割的元素的索引。无论如何，直到函数结束。实际支点值为lst[b]，列表部分中的最后一个元素被分区。该值被移至该函数的最后一行的pivot位置。

pivot值只是“高”值开始的索引。为pivot挑选随机初始值会破坏算法，因为它可能会从列表末尾增加（考虑如果random.randint(a, b)返回b会发生什么情况）。

如果你想有一个随机值来划分左右，选择一个随机指数和运行算法其余为正常（与pivot指数起始于a）之前将其交换价值与lst[b]：

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