python - 我的快速排序 Python 代码有问题吗？

Question

我的快速排序代码遇到问题。

class Sort:
    def quickSort(self, unsortedlist):
        if len(unsortedlist) <= 1:
            return unsortedlist
        pivot = unsortedlist[0]
        unsortedlist.remove(unsortedlist[0])
        left, right = [], []
        for num in unsortedlist:
            if num < pivot:
                left.append(num)
            else:
                right.append(num)
        return self.quickSort(left) + [pivot] + self.quickSort(right)


if __name__ == "__main__":
    a = [76, 76, 65, 72, 58, 64, 82, 3, 22, 31]
    print(Sort().quickSort(a))
    print(Sort().quickSort(a))
    print(Sort().quickSort(a))

结果将是：

[3, 22, 31, 58, 64, 65, 72, 76, 76, 82]
[3, 22, 31, 58, 64, 65, 72, 76, 82]
[3, 22, 31, 58, 64, 65, 72, 82]

为什么排序后的列表越来越少？

标签： pythonsortingquicksort

Answer 1

unsortedlist.remove(unsortedlist[0])

因此，每次调用列表时，都会从源quickSort列表中删除第一个元素。

对于递归调用并不重要，因为您“控制”了列表，但对于每次调用 quickSort 之后的“顶级”调用，您已经“丢失”了其中一个元素。