为什么快排都能tle

彬腾向前冲 @ 2021-08-17 21:07:35

#include <bits/stdc++.h>

using namespace std;

int q[50000001];
int n,k;

void quick_sort(int q[], int l, int r)
{
    if (l >= r) return;

    int i = l - 1, j = r + 1, x = q[(l + r )>> 1];
    while (i < j)
    {
        do i ++ ; while (q[i] < x);
        do j -- ; while (q[j] > x);
        if (i < j) swap(q[i], q[j]);
    }
    quick_sort(q, l, j), quick_sort(q, j + 1, r);
}

int main ()
{
    cin >> n >> k;
    for (int i = 0 ; i < n ; i ++) cin >> q[i];

    quick_sort (q,0,n-1);

    cout << q[k];
}

by 彬腾向前冲 @ 2021-08-17 21:08:15

更玄幻的是 我sort直接过了

by Rainy7 @ 2021-08-17 21:09:07

本题正解不是快排

by pp_orange @ 2021-08-17 21:10:40

quick_sort(q, l, j), quick_sort(q, j + 1, r); 你这行代码有问题

by qwq___qaq @ 2021-08-17 21:11:11

@彬腾向前冲 你用桶试试？（我A了）或者set？（我没试）

by pp_orange @ 2021-08-17 21:14:40

其实有一半的地方是不用排序的,只要排序k所在的那一半，另一边对结果不影响，这题数据是1e6，就是卡快排，用我这个方法就将复杂度由O(nlogn)降到了O（n），详解见本题题解

by Karl_Aurora @ 2021-08-17 21:14:58

@彬腾向前冲 裸快排在处理有序化数据时时间复杂度会退化到 O(n ^ 2) ，sort是进行分类采用快排或插排来进行优化过的

这题正解不是裸快排，换种算法试试

by lxwh @ 2021-08-17 21:22:58

可以试试堆排

by int32 @ 2021-08-17 21:25:13

@彬腾向前冲 用nth_element吧

by int32 @ 2021-08-17 21:25:46

stable_sort 也行

by Mr_ZZzz @ 2021-09-06 08:35:52

用scanf和printf+快排就行。