快速排序是否存在潜在的安全风险?

是的,这是一个安全风险——具体来说是DoS——通过在快速排序中添加递归深度检查,并在达到某个深度时切换到其他内容,可以很容易地减轻这种风险。如果你换成heapsort,你会得到 introsort ,这是许多STL实现实际使用的。

或者,您只需随机化轴元素的选择。

许多快速排序的实现都是使用 randomized version of the algorithm DoS attack 使用精心编制的输入是不可能的。

总的来说,任何使用快速排序的web应用程序都更有可能有其他应用程序 security flaws .

看一下这个问题(和有标记的答案),它讨论了减少QuickSort最坏情况的方法:

Why is quicksort better than mergesort?

如果性能很重要,那么在大多数情况下,无论是否出于安全考虑,快速排序似乎都是一个糟糕的选择。有没有什么东西会让你回避像Heapsort或Mergesort这样的算法?

我认为这在很大程度上是一个问题,你实际上在哪里使用快速排序。例如,在处理5个项目的数组时,使用O(n^2)算法是非常好的。另一方面,当数据可能非常大时,担心DoS并不是你要面对的第一个问题——第一个问题是在你面对真正的问题之前性能会变得很差。考虑到大量其他可用的算法,如果它位于关键位置,请更换它。

是的,但只有在非常、非常不可能的情况下——所有这些都是一个适当设计的算法很容易避免的。

但是如果你想超级安全,你可能想使用 Introsort ,它以快速排序开始,但如果从递归深度检测到算法开始变为二次排序,则会切换到堆排序。

我看到帕维尔打败了我。

针对编辑后的问题: