Quicksort最坏的情况是什么？

Quicksort最坏的情况是什么？

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

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

为了避免出现这种极端情况，对标准的快速排序算法进行了一些修改-一个示例是已集成到Java
7中的双轴快速排序。