什么是“快速排序的杀手级对手”？
What is " killer adversary for quick sort "?
我已经阅读了快速排序。我们使用枢轴元素而不考虑数组中的其他数据集。据我所知;这个杀手级对手告诉输入导致二次时间复杂度（实际上）。但是怎么办？
编辑：来自 published paper 的 Adversary killer for Quick Sort 的以下几行不理解。
" 最初对手使所有物品 gas.When 两个气体物品被比较，一个被“冻结”成
一个确定的“固定”值，大于任何已经固定的值。然后重新比较操作数。
当固体物品与气体物品进行比较时，它比较low.When 两个固体物品进行比较，
答案取决于冻结值。"
将 "gas" 和 "solid" 视为对手应用于数组项的标签，以便记住快速排序已经看到了哪些项。对手是这样工作的：
- 对手给出了一组标记为 "gas" 且值为正无穷大的项目进行快速排序；
- 快速排序选择它希望比较的项目；
- 对手可能会介入，将 "gas" 标签更改为 "solid" 标签，为项目赋予有限整数值，然后允许快速排序继续进行。
该过程的设计使得只有在快速排序尚未移动项目时才能冻结该项目。因此，如果我们在所有项目都是固定的之后取出这些项目，将它们按原来的顺序排列，然后在没有对手的情况下将它们交给快速排序，那么快速排序将使用与对手存在时完全相同的比较顺序。
该论文假设对手具有不寻常的能力：对手控制了 quicksort 调用的比较函数 。换句话说，对手不仅可以在开始时提供恶意制作的数据数组，还可以在 quicksort 运行.
期间调整其行为
鉴于这种能力，对手可以有效地构造一个输入数组 'on-the-fly'（正如 quicksort 观察到的那样），其中每个枢轴被选择为具有比之前观察到的所有元素更高的值.这样，选择了 n 个枢轴，并将每个枢轴与 O(n) 个元素进行比较，得到 O(n^2) 的 运行 时间。
'on-the-fly' 功能还允许打破 quicksort 的随机版本。但是，除非你提供在线排序服务，攻击者同时提供输入和比较方法，否则你不必担心这种攻击。
我已经阅读了快速排序。我们使用枢轴元素而不考虑数组中的其他数据集。据我所知;这个杀手级对手告诉输入导致二次时间复杂度（实际上）。但是怎么办？
编辑：来自 published paper 的 Adversary killer for Quick Sort 的以下几行不理解。
" 最初对手使所有物品 gas.When 两个气体物品被比较，一个被“冻结”成 一个确定的“固定”值，大于任何已经固定的值。然后重新比较操作数。 当固体物品与气体物品进行比较时，它比较low.When 两个固体物品进行比较， 答案取决于冻结值。"
将 "gas" 和 "solid" 视为对手应用于数组项的标签，以便记住快速排序已经看到了哪些项。对手是这样工作的：
- 对手给出了一组标记为 "gas" 且值为正无穷大的项目进行快速排序；
- 快速排序选择它希望比较的项目；
- 对手可能会介入，将 "gas" 标签更改为 "solid" 标签，为项目赋予有限整数值，然后允许快速排序继续进行。
该过程的设计使得只有在快速排序尚未移动项目时才能冻结该项目。因此，如果我们在所有项目都是固定的之后取出这些项目，将它们按原来的顺序排列，然后在没有对手的情况下将它们交给快速排序，那么快速排序将使用与对手存在时完全相同的比较顺序。
该论文假设对手具有不寻常的能力：对手控制了 quicksort 调用的比较函数 。换句话说，对手不仅可以在开始时提供恶意制作的数据数组，还可以在 quicksort 运行.
鉴于这种能力，对手可以有效地构造一个输入数组 'on-the-fly'（正如 quicksort 观察到的那样），其中每个枢轴被选择为具有比之前观察到的所有元素更高的值.这样，选择了 n 个枢轴，并将每个枢轴与 O(n) 个元素进行比较，得到 O(n^2) 的 运行 时间。
'on-the-fly' 功能还允许打破 quicksort 的随机版本。但是，除非你提供在线排序服务，攻击者同时提供输入和比较方法，否则你不必担心这种攻击。