algorithm - 快速排序是“自适应”和“在线”的吗？

Question

也就是说，当给定一个已经排序的列表时，Quicksort 的性能会更好吗？我不明白为什么会这样，但也许我不完全理解算法。

此外，当我们在排序时将新数据添加到列表中时，快速排序能否“继续”？在我看来，该算法一开始就需要全套所有数据才能“工作”。

Answer 1

当给定一个已经排序的列表时，快速排序会更好吗？

不，实际上它通常教授的方式（使用第一个元素作为枢轴）已经排序（或接近排序）的列表是最坏的情况。但是，使用中间元素或随机元素作为枢轴可以缓解这种情况。

当我们在排序时将新数据添加到列表中时，快速排序可以“继续”吗？

不，您的直觉是正确的，您从一开始就需要整个数据集。

Answer 2

快速排序，当它的枢轴选择是随机的时，运行时间为 O(n lg n)，其中 n 是数组的大小。如果它选择的枢轴是按排序顺序的，它的运行时间会降到 O(n^2)。无论您是从左侧、右侧、中间还是随机选择枢轴，都没有关系，因为即使不可能，也可以按排序顺序选择枢轴。

避免这种情况的唯一方法是通过使用诸如“三的中位数”之类的技术来保证枢轴不按顺序排列。

根据 Robert Sedgewick，Algorithms，Addison-Wesley Publishing Company，1988 年，第 124 页，如果您使用三的中位数技术来选择枢轴并停止小分区的递归（从 5 到 25 的大小；这会留下数组未排序，但您可以使用插入排序快速完成它）然后快速排序将始终为 O(n lg n)，此外，运行速度比普通快速排序快 20%。

Answer 3

给定已排序的列表时，快速排序是否执行得更好

我认为快速排序的性能主要取决于每一步中枢轴元素的选择。如果选择的枢轴元素可能是列表中最小或最大的元素，那将是最糟糕的

快速排序“继续”，同时我们将新数据添加到列表中 排序时？

是的，快速排序不是自适应的。这就是快速排序的特性。