我只是想知道(在某些严重的偏执狂和某些情况下)使用 QuickSort 算法是否可以被视为应用程序中的安全风险。
它的基本实现和改进版本(如 3-median-quicksort)都具有对某些输入数据表现异常的特性，这意味着它们的运行时间在这些情况下会大大增加(O(n^ 2) 复杂性)更不用说 stackoverflow 的可能性了。
因此，我认为向程序提供预先排序的数据可能会造成危害，这会导致算法像这样运行，这可能会产生不可预知的后果，例如多客户端 Web 应用程序。
这种奇怪的情况是否值得任何安全考虑(因此会迫使我们改用Intro- 或Mergesort)？
编辑:我知道有一些方法可以防止 Quicksort 的最坏情况，但是语言集成排序(如 .NET 的 3-Median)呢？他们会成为禁忌吗？
最佳答案
是的，这是一种安全风险 - 具体来说是 DoS - 通过在快速排序中添加递归深度检查并在达到一定深度时切换到其他方式来轻松缓解这种风险。如果你切换到堆排序，那么你会得到 introsort ，这是许多 STL 实现实际使用的。
或者，您只是随机选择枢轴元素。
关于algorithm - Quicksort 是否存在潜在的安全风险？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/1527136/