algorithm - 为什么 QuickSort 不擅长对几乎已排序的数据进行排序

Question

<分区>

Answer 1

根据枢轴的选择，您的陈述对于 QS 的某些变体是正确的。 QS 性能取决于旋转操作，将数据划分为大小大致相等的 block ，然后分别对这些 block 进行排序。如果主元是数据的最小值或最大值，或者表示高或低百分位数，则主元运算会将数据分为两部分，其中大部分数据位于两者之一中，但仍需要对其进行排序。如果选择数据的第一个元素作为主元，并且对数据进行排序，则会发生这种最坏情况。通过仅选择一个随机元素作为基准，最坏情况发生的可能性可以忽略不计。这与最坏情况分析无关，但平均而言(在可能的枢轴上，最坏情况下输入)或在实践中这会产生良好的性能。