快速sorting最坏的情况
我正在研究下面需要的程序来更好地理解它。
什么是Quicksort最糟糕的情况下运行时间，什么可能会导致这种情况下更糟糕的performance？ 我们如何修改quicksort程序来解决这个问题？
我知道它有最坏的情况O（n ^ 2），我知道它发生时，枢轴唯一最小或最大元素。 我的问题是如何修改程序来缓解这个问题。
一个好的algorithm会很好。
谢谢
Quicksort的性能取决于您的数据透视selectalgorithm。 最天真的枢轴selectalgorithm是只select第一个元素作为你的支点。 很容易看出，如果你的数据已经被sorting，那么这会导致最糟糕的行为（第一个元素总是最小的）。
有两种常见的algorithm可以解决这个问题：随机select一个数据透视表，或者select三位数的中位数。 随机是显而易见的，所以我不会详细介绍。 三个中间值涉及select三个元素（通常是第一个，中间和最后），并select这三个元素的中位数作为关键点。
由于随机数发生器通常是伪随机的（因此是确定性的）并且三个algorithm的非随机中值是确定性的，所以可以构造导致最坏情况行为的数据，但是在正常使用情况下很less出现。
您还需要考虑性能影响。 你的随机数发生器的运行时间会影响你的快速sorting的运行时间。 中位数为三，你正在增加比较的数量。
最差的performance条件：
当每次select枢纽是“最大”或“最小”，这种模式重复
所以为1 3 5 4 2
如果枢轴按顺序select1,2,3,4,5或5,4,3,2,1
那么最坏的情况下运行时间是O（n * n）
如何避免最糟糕的情况：
（1）将数组分成5组，如果1..100组（1..20）（21..40）（41..60）（61..80）（81..100）
（2）选取（3）（23）（43）（63）（83）
（3）现在select中位数作为支点，所以在这里它的（43）
一个简单的修改就是随机select枢轴。 这可能性很高，效果很好。
这已经有一段时间了，但是我认为快速sorting最糟糕的情况是数据已经sorting。 快速检查数据是否已经sorting可以帮助缓解这个问题。
最差的运行时间取决于快速sorting中的分区方法。 这有两个方面：
- select枢轴
- 如何围绕枢轴分区
在以前的文章（中位数，三位或随机化的中位数）中select了关键的好策略。 但是，即使明智地select了数据透视表，如果一个数组具有所有相同的元素，那么如果只有两个分区被构build，将会导致最糟糕的运行时间，因为一个数组将携带相等的元素，即所有元素：
- 这导致分区被称为n次，每次平均n / 2导致O（n2）
- 这是不好的，因为这不是一个理论上最坏的情况，而是一个相当普遍的情况
- 请注意，它不是通过检测空分区来解决的，因为主键可能具有最高或最低的元素值（例如，中位数是5，这也是最高元素值，但仍然可能存在一些错位<5个值）
一个解决这个问题的方法是分成三个分区，一个较低（元素<透视），一个平等（元素=透视）和一个上部分区。 “=主元素”处于最终位置。 如果不是空的，则需要将较低和较高的分区sorting。
与随机化一起，中位数的中位数或某种组合select一个数据透视表是一个最坏的情况是相当罕见的，但并非不可能，这使algorithm的最坏情况下O（n2）的上限。
