Nik*_*chi 34
Quicksort的性能取决于您的枢轴选择算法.最天真的枢轴选择算法是选择第一个元素作为您的支点.如果您的数据已经排序(第一个元素将始终为最小值),很容易看出这会导致最坏的情况.
有两种常见的算法可以解决这个问题:随机选择一个支点,或选择三个中位数.随机是显而易见的,所以我不会详细介绍.三个中位数涉及选择三个元素(通常是第一个,中间和最后一个)并选择那些元素的中位数作为支点.
由于随机数生成器通常是伪随机的(因此是确定性的)并且三个算法的非随机中值是确定性的,因此可以构造导致最坏情况行为的数据,但是它在正常使用中很少出现.
您还需要考虑性能影响.随机数生成器的运行时间将影响快速排序的运行时间.中位数为3,您正在增加比较次数.
the*_*ick 10
最糟糕的表现条件:
当每次选择的枢轴都是"最大"或"最小"时,这种模式会重复出现
所以对于1 3 5 4 2
如果按1,2,3,4,5或5,4,3,2,1的顺序选择枢轴
那么最坏的情况是运行时间是O(n*n)
如何避免最坏的情况:
(1)将数组分为五组.如果1..100 则为(1..20)(21..40)(41..60)(61..80)(81..100)
(2)选择每组中前五个元素的中位数,如此(3)(23)(43)(63)(83)
(3)现在选择它们中间作为枢轴,所以这里(43)
已经有一段时间了，但我认为快速排序最糟糕的情况是数据已经排序。快速检查数据是否已排序可以帮助缓解此问题。