python递归快速排序算法

2022-05-21 07:37:49 发布

您现在位置:Python中文网/ 问答频道 /正文

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

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

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


Tags: 代码in算法ifdefquicksortstartendpivotpartition小时arrquicksortpindex
1条回答
网友
1楼 ·

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

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

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