快速排序递归 [英] Quick Sort Recursion

问题描述

我正在尝试追踪这个快速排序算法:

I'm trying to trace this quick sort algorithm:

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

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

But with a different set of numbers - [6,2,8,4,3,7,10]

算法左侧排序后就好了，但是后面的递归类就看不懂了.

I'm fine once the left side of the algorithm is sorted, but I don't understand the recursion class after that.

一旦左侧完成并且start = 0 和end = 0，运行以下行:

Once the left side is completed and start = 0 and end = 0, the following line runs:

 quicksort(myList, pivot+1, end)

当我从快速排序功能中打印出开始和结束值时:

When I print out the start and end values from the quick sort function:

Start = 2 and End = 1
Start = 3 and End = 2
Start = 4 and End = 6

我不明白 start 和 end 如何变成这些值.

I don't understand how the start and end change to these values.

谁能解释一下如何以及为什么?

Can anyone explain how and why?

推荐答案

您可能会考虑更简单地实现快速排序.例如，

You might consider a easier implementation of quicksort. For example,

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.然后遍历列表，如果元素大于主元 (52)，则将其放入高"分区，如果小于 52，则将其放入低"分区.此时经过一次运行(在我们运行 high = quicksort(high) 之前)，我们有

This rather simple implementation is easy to explain. You are partitioning a list based on an arbitrary choice of the pivot. In this case arr[0] = 52. You then are iterating through the list and if the element is greater than the pivot (52), you put it into the 'high' partition and if it's less than 52, you're putting it into the 'low' partition. At this point after one run through (before we run high = quicksort(high)), we have

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

然后我们在低"和高"分区上运行这个快速排序功能.例如，对于高分区，pivot = arr[0] = 56.我们遍历高分区，如果元素小于枢轴(56)，我们将其放入一个新的低分区组，该组是高分区的子组.如果元素大于56，那么我们把它放在一个新高分区，它是高分区的一个子组.你可以把它想象成从一个我们想要排序的列表开始，然后分支成一个高分区和一个低分区，然后每个分区都分支成自己的高分区和低分区.这就是递归的用武之地

We then run this quicksort function on the 'low' and 'high' partitions. For example, for the high partition, pivot = arr[0] = 56. We iterate through the high partition, and if the element is less than the pivot(56), we put it in a new low partition group that is a subgroup of the high partition. If the element is greater than 56, then we put it in a new high partition that is a subgroup of the high partition. You can think of it as starting with one list that we want to sort and branching off into a high partition and a low partition which then each branch into their own high and low partitions. That's where the recursion comes in

这篇关于快速排序递归的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！