@[jingkongwanglimiaoa](/user/222578) 就是快排的思想，但是交换完之后不可能为答案的一边直接舍去，使得平均复杂度为 $O(n)$。 但是这题它的分界点是随机的，所以最坏会被退化到 $(n^2)$。 by Utilokasteinn @ 2021-09-17 07:52:48