如果快速排序算法中的第一个元素恰好是最小值,该怎么办

Question

我试着通过我可爱的教科书(没有用)和在线查看.根据我正在Cormen工作的书,我们将使用数组中的第一个元素作为支点.我只是坚持要做什么,因为第一个元素恰好是1.
数组看起来如下:
[1,16,2,3,14,5,12,7,10,5,9,17,19 ,21,23,26,27]
同样,书中算法的问题在于它选择第一个元素作为枢轴.并且一旦我们将1与所有其他元素进行比较并发现没有其他元素小于或等于那么我们将交换枢轴和子数组的中间元素,其中左边的子阵列小于枢轴并且右边的子阵列大于枢轴.但如果我们的支点是1,那么我们就无法交换.真的很困惑,任何帮助都会很棒.这本书的标题是"算法入门"第3版,以防有人熟悉它.

Answer 1

与正常情况没有区别:只需将左侧部分视为空,并在右侧部分进行快速排序,这是1的子阵列.

这不是一个特例.事实上,当输入被排序时,天真的快速排序退化为O(N^2)排序算法.引用维基百科:

在快速排序的早期版本中,通常会选择分区的最左边元素作为枢轴元素.不幸的是,这会导致已经排序的数组的最坏情况行为,这是一个相当常见的用例.通过选择枢轴的随机索引,选择分区的中间索引或(特别是对于较长的分区)选择分区的第一个,中间和最后一个元素的中位数(如建议的那样),可以轻松解决问题. R. Sedgewick).