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

Question

我试着浏览我可爱的教科书（无济于事）和在线。根据我正在由 Cormen 编写的书，我们将使用数组中的第一个元素作为枢轴。因为第一个元素恰好是 1，所以我只是坚持要做什么。
数组如下所示：
[1, 16, 2, 3, 14, 5, 12, 7, 10, 8, 9, 17, 19 , 21, 23, 26, 27]
同样，书中算法的问题在于它选择第一个元素作为枢轴。一旦我们将 1 与所有其他元素进行比较并发现没有其他元素小于或等于，那么我们将交换枢轴和子数组的中间元素，其中左侧的子数组小于枢轴并且右边的子数组大于枢轴。但如果我们的支点为 1，那么我们就无法交换。真的很困惑，任何帮助都会很棒。这本书的标题是Introduction to Algorithms, 3rd Edition，以防有人熟悉它。

Answer 1

与正常情况没有区别：只需将左侧部分视为空，并对右侧部分进行快速排序，右侧部分是 1 的子数组。

这不是特例。事实上，当对输入进行排序时，朴素的快速排序会退化为O(N^2)排序算法。引用维基百科：

在快速排序的早期版本中，分区的最左侧元素通常会被选为枢轴元素。不幸的是，这会导致已经排序的数组出现最坏情况，这是一个相当常见的用例。通过为枢轴选择随机索引，选择分区的中间索引或（特别是对于较长的分区）为枢轴选择分区的第一个，中间和最后一个元素的中值（如推荐的那样），这个问题很容易解决R.塞奇威克）。

Answer 2

你可以使用被称为三法则的东西。选择数组中的第一个值、中间值和最后一个值，然后选择其中一个作为枢轴候选。这并不能保证您将获得最佳支点，但它会降低获得非常糟糕支点的机会。