快速排序 最坏情况 [英] Quick sort Worst case

问题描述

我正在编写下面需要的程序，以便更好地理解它.

I'm working on the program just needed in the following to understand it better.

Quicksort 最坏情况下的运行时间是多少，什么可能导致这种更坏情况下的性能?我们如何修改快速排序程序来缓解这个问题?

What is the worst case running time for Quicksort and what may cause this worse case performance? How can we modify quicksort program to mitigate this problem?

我知道它有最坏的情况 O(n^2) 并且我知道它发生在枢轴唯一的最小或最大元素时.我的问题是如何修改程序来缓解这个问题.

I know that it has worst case O(n^2) and I know it occurs when the pivot unique minimum or maximum element. My question is how can I modify the program to mitigate this problem.

好的算法会很好.

推荐答案

Quicksort 的性能取决于您的枢轴选择算法.最简单的支点选择算法是只选择第一个元素作为你的支点.很容易看出，如果您的数据已经排序(第一个元素将始终是最小值)，这会导致最坏的行为.

Quicksort's performance is dependent on your pivot selection algorithm. The most naive pivot selection algorithm is to just choose the first element as your pivot. It's easy to see that this results in worst case behavior if your data is already sorted (the first element will always be the min).

解决这个问题常用的算法有两种:随机选择一个pivot，或者选择三个的中位数.随机是显而易见的，所以我不会详细介绍.三的中位数涉及选择三个元素(通常是第一个、中间和最后一个)并选择这些元素的中位数作为主元.

There are two common algorithms to solve this problem: randomly choose a pivot, or choose the median of three. Random is obvious so I won't go into detail. Median of three involves selecting three elements (usually the first, middle and last) and choosing the median of those as the pivot.

由于随机数生成器通常是伪随机的(因此是确定性的)并且三个算法的非随机中位数是确定性的，因此有可能构建导致最坏情况行为的数据，但很少出现正常情况用法.

Since random number generators are typically pseudo-random (therefore deterministic) and a non-random median of three algorithm is deterministic, it's possible to construct data that results in worst case behavior, however it's rare for it to come up in normal usage.

您还需要考虑性能影响.你的随机数生成器的运行时间会影响你的快速排序的运行时间.中位数为 3，您增加了比较次数.

You also need to consider the performance impact. The running time of your random number generator will affect the running time of your quicksort. With median of three, you are increasing the number of comparisons.

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