题目描述
blablabla
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
int quick_sort(int q[], int l, int r, int k) {
if (l == r) return q[l];
int i = l - 1, j = r + 1, x = q[l + (r-l) / 2]; // 选区间中点做pivot
while (i < j) {
do i++; while (q[i] < x);
do j--; while (q[j] > x);
if (i < j) swap(q[i], q[j]);
}
int len = j - l + 1; // 此时j和i相等,就是pivot,pivot左边的数<= pivot; 右边>= pivot
if (j - l + 1 >= k) // target 在左侧
quick_sort(q, l, j, k);
else // target在右侧
quick_sort(q, j + 1, r, k - len);
}