我的印象是随机数据导致快速排序退化的概率呈指数级小，但找不到它的公式。
当然，已经排序的数据会导致简单的快速排序很容易退化。
是否有典型的数据不是对手，但会触发 3 中位数快速排序的 O(n^2) 行为（通常的低高中中位数）？
随机数据导致快速排序进行超过（例如）2 n log_2(n) 次比较的概率是多少？
最后一个问题很有趣，因为典型的 C++ STL 使用 introsort，它使用类似的阈值更改为备份算法。
您要求的概率非常小——随机选择的数据极不可能导致快速排序非常糟糕的行为。
但是，现实世界的数据不是随机的。相关问题是是否存在“某些数据模式”会导致快速排序出现“不完全随机”的问题，因此在实践中可能会出现问题。 这就是已排序数据和先枢轴快速排序的情况。这是一种根本不是随机的数据模式，因此在实践中很可能发生，这就是为什么它是一个问题。 任何中位数为 3 的快速排序是否存在类似的问题模式？是的，当然。如果您与对手建立这样的模式，那么您会发现它根本不是随机的，因此可能出现在真实数据中。
需要对手破解你的算法的论点只适用于随机算法。例如，如果您的哈希函数是从所有可能的哈希函数中随机选择的，那么对手就需要破坏您的哈希表。