快排杀手：如何让非随机化快排效率降至平方级

“快排杀手(把非随机化的快排卡到平方级).A Killer Adversary for Quicksort - M. D. MCILROY - 软件实践与经验，第29卷，1-4页(1999年)” 在计算机科学领域，快速排序是一种广泛应用的排序算法，以其平均情况下的高效性能而著名。然而，快速排序在最坏情况下的时间复杂度是O(n²)，这通常发生在输入数据已经部分排序或完全有序的情况下。M. D. MCILROY在“快排杀手：一个针对标准C qsort函数的特殊对手”这篇论文中，探讨了一种方法，即使面对非随机化的快速排序实现，也能使其性能退化到平方级的时间复杂度。 快速排序的基本思想是选择一个“枢轴”元素，然后将数组分为两部分，一部分包含所有小于枢轴的元素，另一部分包含所有大于或等于枢轴的元素。理想情况下，枢轴的选择应该是随机的，以确保平均时间复杂度保持在O(n log n)。但在实际应用中，快速排序可能遇到特定的输入序列，这些序列可以被设计来挑战算法，使其效率降低。 MCILROY提出的这种“杀手对手”策略，通过动态构造输入序列，根据快速排序在比较过程中选择的元素来调整输入，使得每次划分的效果都不利于算法。例如，当算法试图将枢轴放在已经排序的序列中时，这种策略会迫使算法做出不利于其性能的决策。这种方法不仅适用于标准的C qsort函数，而且对任何满足某些非常温和且实际的假设的快速排序实现都有效，包括那些尝试通过随机化枢轴选择来避免最坏情况的实现。 尽管大多数算法书籍都会提到如何处理低熵（即有序或接近有序）输入的策略，比如三向切分快速排序，但现实世界中的生产环境中，快速排序仍然可能在特定输入下陷入平方级的时间复杂度。MCILROY的这种对抗性方法揭示了即使是精心优化的快速排序实现，也无法完全避免在某些特定输入上的性能退化。 文章中指出，像标准C库中的qsort这样的多态快速排序实现，由于不考虑数据的性质而直接进行排序，更容易受到这种攻击。为了防御这种攻击，开发者可能需要牺牲速度来增加额外的复杂性，例如，通过引入随机化机制来防止输入的恶意构造。然而，这并不总是可行的，因为快速排序的速度优势可能因此而减损。 “快排杀手”的概念提醒我们，虽然快速排序在大多数情况下表现优秀，但在设计和实现时必须考虑到潜在的最坏情况。对于实际应用中的快速排序算法，除了关注平均性能，还需要考虑如何处理可能的恶意输入，以确保在各种情况下的稳定性与效率。