python递归快速排序算法

Question

我已经试着调试我的代码好几个小时了，但是没有任何进展。我喜欢有人能帮我，我刚开始学习算法

def quicksort(arr):
    start = 0
    end = len(arr) - 1
    quick_sort(arr, start, end)


def quick_sort(arr, start, end):
    if start < end:
        pindex = partition(arr, start, end)
        quick_sort(arr, start, pindex)
        quick_sort(arr, pindex+1, end)


def partition(arr, start, end):
    pivot = arr[end]
    i = start
    for j in range(start, end):
        if arr[j]<= pivot:
            arr[i], arr[j] = arr[j], arr[i]
            i += 1
    arr[i], arr[end] = pivot, arr[i]
    return i;

当我用quicksort([6,4,5,4,2,43,1,4,532,515,243,3,34,5,12,24,234,45,6,457,5])运行它时

我明白了

RecursionError: maximum recursion depth exceeded in comparison

我很确定我在快速排序函数的开头使用了一个基本情况

Answer 1

您的quicksort和quick_sort例程使用要排序的子数组中第一个和最后一个项的索引作为参数。在划分子数组之后，需要对两部分进行排序。但是，在调用的第一部分中包含分区的pivot元素。你应该把pivot元素去掉，所以使用quick_sort(arr, start, pindex-1)

试试看。您没有注释，因此很难调试程序。您的示例输入也太大，难以轻松调试。尝试一个空数组，然后是一个包含一个元素的数组，然后是一些包含两个元素的数组，依此类推，以捕获错误

有了这个改变，你的程序现在通过了我所有的测试