我读过快速排序。我们使用主元元素，而不考虑数组中的其他数据集。据我所知;这个 killer 级对手告诉我们导致二次时间复杂度(实际上)的输入。但如何呢？
编辑:以下几行来自 published paper关于快速排序的对手 killer 不明白。
"最初，对手将所有元素变成气体。当比较两个气体元素时，其中一个会被“卡住”成 一个明确的“固定”值，大于任何已经固定的值。然后重新比较操作数。 当固体元素与气体元素比较时，它比较低。当比较两个固体元素时， 答案取决于卡住值。”
最佳答案
将“气体”和“固体”视为对手应用于数组项目的标签，以便记住快速排序已经看到了哪些项目。对手的工作方式如下:
- 对手给出了一系列标记为“gas”且值为正无穷的项目进行快速排序；
- 快速排序选择要比较的项目；
- 对手可能会进行干预，将“气体”标签更改为“固体”标签，为该项目指定一个有限整数值，然后允许快速排序继续进行。
该过程的设计使得只有在快速排序尚未移动项目时才能卡住该项目。因此，如果我们在所有项目都固定后取出它们，按原始顺序排列它们，然后在没有对手的情况下对它们进行快速排序，则快速排序将使用与对手在场时完全相同的比较顺序。
关于algorithm - "killer adversary for quick sort "是什么？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/36383788/