Quicksort最坏的情况是什么？ [英] What is the worst case scenario for quicksort?

问题描述

quicksort算法什么时候需要O（n ^ 2）时间？

When does the quicksort algorithm take O(n^2) time?

推荐答案

Quicksort通过枢轴工作，然后将所有低于该元素的元素放在一边，而所有较高的元素放在另一端；然后，它以相同的方式递归地对两个子组进行排序（一直向下直到所有内容都被排序。）现在，如果您每次都选择最差的数据透视表（列表中的最高或最低元素），则只有一组排序，以及该组中除您选择的原始数据透视表之外的所有内容。从本质上讲，这使您可以将n个组重复进行n次，因此复杂度为O（n ^ 2）。

Quicksort works by taking a pivot, then putting all the elements lower than that pivot on one side and all the higher elements on the other; it then recursively sorts the two sub groups in the same way (all the way down until everything is sorted.) Now if you pick the worst pivot each time (the highest or lowest element in the list) you'll only have one group to sort, with everything in that group other than the original pivot that you picked. This in essence gives you n groups that each need to be iterated through n times, hence the O(n^2) complexity.

发生这种情况的最常见原因是如果将枢轴选择为quicksort实现中列表的第一个或最后一个元素。对于未排序的列表，这和其他列表一样有效，但是对于已排序或几乎已排序的列表（在实践中很常见），很可能会给您带来最坏的情况。这就是为什么所有半体面的实现都倾向于从列表的中心出发。

The most common reason for this occurring is if the pivot is chosen to be the first or last element in the list in the quicksort implementation. For unsorted lists this is just as valid as any other, however for sorted or nearly sorted lists (which occur quite commonly in practice) this is very likely to give you the worst case scenario. This is why all half-decent implementations tend to take a pivot from the centre of the list.

标准quicksort算法进行了修改，以避免出现这种情况-一种示例是集成的双轴快速排序进入Java 7 。

There are modifications to the standard quicksort algorithm to avoid this edge case - one example is the dual-pivot quicksort that was integrated into Java 7.

这篇关于Quicksort最坏的情况是什么？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！