快速排序未返回预期结果Python3

Question

我一直在研究一种快速排序算法，该算法专门将墙设置在左侧，将当前元素设置在墙的右侧，并将轴设置在数据集的末尾。 排序会将当前元素与透视图进行比较，并在每次大于透视图时递增当前元素。当它小于或等于轴时，它应将当前元素与墙右侧的项交换，并将墙向右移动一处。你知道吗

这是我的密码：

def QuickSort(dataset, low, high):
    if (low >= high):
        return dataset
    else:
        #Set pivot to last element
        pivot = high
        #Set wall at first element
        wall = low
        #Loop through list - if current element is less or equal
        #to the pivot, swap current element with element right of wall
        #and move wall on.
        for i in range(high):
            if (dataset[i] <= pivot):
                temp = dataset[wall]
                dataset[wall] = dataset[i]
                dataset[i] = temp
                wall = wall + 1
                if wall >= high:
                    break

        #recursively call for subsequent part of list
        QuickSort(dataset, low, wall-1)
        QuickSort(dataset, wall, high)

dataset = [1,6,2,3,6,7,4,2,5]
dataset_length = len(dataset)
sorted_data = QuickSort(dataset, 0, dataset_length)
print(sorted_data)

input()

在运行代码时，数据集没有返回，我也看不出哪里出错了。谢谢你的帮助。你知道吗

Answer 1

pivot = high

这不会将轴心点设置为列表中的最后一个元素。相反，它将枢轴设置为数据集的长度，即9。所以把它改成dataset[high - 1]就行了。你知道吗

此外，搜索大于pivot或小于pivot的元素所需的范围不是range(high)，而是range(low, high)，因为当深入递归时，列表的大小以及它的起始和结束索引都会发生变化。你知道吗

def QuickSort(dataset, low, high):
    if (low >= high):
        return
    #Set pivot to last element
    pivot = dataset[high - 1]
    #Set wall at first element
    wall = low
    #Loop through list - if current element is less or equal
    #to the pivot, swap current element with element right of wall
    #and move wall on.
    for i in range(low, high):
        if (dataset[i] <= pivot):
            temp = dataset[wall]
            dataset[wall] = dataset[i]
            dataset[i] = temp
            wall = wall + 1
            if wall >= high:
                break
         #recursively call for subsequent part of list
    QuickSort(dataset, low, wall - 1)
    QuickSort(dataset, wall, high)

dataset = [1,6,2,3,6,7,4,2,5]
dataset_length = len(dataset)
QuickSort(dataset, 0, dataset_length)
print(dataset)