快速排序递归

Question

我试图追踪这个快速排序算法：

https://pythonschool.net/data-structures-algorithms/quicksort/

但是有一组不同的数字-[6,2,8,4,3,7,10]

一旦算法的左边被排序，我就没事了，但是我不理解之后的递归类。在

一旦左侧完成并且start = 0和end = 0，下面的行将运行：

 quicksort(myList, pivot+1, end)

当我从快速排序函数打印出起始值和结束值时：

^{pr2}$

我不明白start和end如何改变为这些值。在

有人能解释一下为什么吗？在

Answer 1

您可以考虑使用更简单的快速排序实现。例如

my_list = [52,8,45,43,6,56,76,36,54,12,34,98,41,30]

def quicksort(arr):
    high = []
    low = []
    pivot_list = []

    if len(arr) <= 1:
        return arr
    else:
        pivot = arr[0]
        for i in arr:
            if i < pivot:
                low.append(i)
            elif i > pivot:
                high.append(i)
            else:
                pivot_list.append(i)
        high = quicksort(high)
        low = quicksort(low)

    return low + pivot_list + high

print quicksort(my_list)

[6, 8, 12, 30, 34, 36, 41, 43, 45, 52, 54, 56, 76, 98]

这个相当简单的实现很容易解释。 您正在根据任意选择的轴对列表进行分区。在本例中，arr[0] = 52。然后遍历列表，如果元素大于pivot（52），则将其放入“high”分区，如果小于52，则将其放入“low”分区。在一次运行之后（在运行high = quicksort(high)之前），我们已经

^{pr2}$

然后在“低”和“高”分区上运行这个快速排序函数。例如，对于高分区，pivot = arr[0] = 56。我们迭代高分区，如果元素小于轴（56），我们将其放入一个新的低分区组，它是高分区的一个子组。如果元素大于56，那么我们把它放在一个高分区的子群中。你可以把它看作是从一个列表开始，我们想对它进行排序，然后把它分成一个高分区和一个低分区，然后每个分区又分到各自的高分区和低分区。这就是递归的原因