arrays - 快速排序分区 Python

Question

我的快速排序有些问题。这是我的程序:

def main():
     Array = [10, 5, 3, 8, 6, 7, 4, 9, 2, 1, 10]
     right_index = (len(Array) - 1)
     left_index = 0
     Quicksort(Array, left_index, right_index)

def Quicksort(Array, left_index, right_index):
    if len(Array) == 1:
        return Array
    pivot_index = Partition(Array, left_index, right_index)
    Quicksort(Array, left_index, pivot_index-1)
    Quicksort(Array, pivot_index + 1, right_index)
    return Array

def Partition(Array, left_index, right_index):
    pivot = Array[left_index]
    i = left_index + 1
    for j in range(left_index + 1, right_index):
        if Array[j] <= pivot:
            Array[j], Array[i] = Array[i], Array[j]
            i += 1
    Array[left_index], Array[i - 1] = Array[i - 1], Array[left_index]
    return i - 1

main()

我做错了什么吗？我收到错误:for j in range(left_index + 1, right_index):

RecursionError:比较时超出最大递归深度。

感谢任何人可能提供的帮助。

Answer 1

当您遇到递归错误时，通常是您的终止条件有问题。 (这就是 moghya 试图告诉你的，尽管不是很清楚。)在你的情况下:

if len(Array) == 1:
    return Array

您使用两个索引来跟踪您当前正在处理的子数组。基本数组 Array 的长度始终为 11；您对该数组所做的唯一更改是交换元素。因此，你的终止条件应该是:

if left_index >= right_index:
    return Array

您的代码中还有另一个错误:当您对数组进行分区时，您错过了最后一个元素。这里:

for j in range(left_index + 1, right_index):

上限应该是right_index + 1。这个差一个错误可能是因为您选择使用包含上限，即 right_index 是最后一个有效索引。

这不是 Python(和许多其他语言)处理数组的方式。 Python 数组和范围具有包含性下限和独占性上限。从零开始的索引和独占上限乍一看似乎有点违反直觉，但我建议您接受而不是反对这一惯例。

我还建议您编写一个包装器快速排序函数，它不需要显式传入数组绑定(bind)。将所有这些放在一起，您将得到:

def main():
     Array = [10, 5, 3, 8, 6, 7, 4, 9, 2, 1, 10]
     quicksort(Array)

     print Array

def quicksort(a):
    quicksort_sort(a, 0, len(a))
    return a

def quicksort_sort(a, left, right):
    if left + 1 < right:
        ipivot = quicksort_part(a, left, right)    
        quicksort_sort(a, left, ipivot)
        quicksort_sort(a, ipivot + 1, right)

def quicksort_part(a, left, right):
    pivot = a[left]
    i = left + 1

    for j in range(left + 1, right):
        if a[j] <= pivot:
            a[j], a[i] = a[i], a[j]
            i += 1

    a -= 1
    a[left], a[i] = a[i], a[left] 

    return i

main()