请问我这个不是快速排序吗,怎么也超时了呢

P1923 【深基9.例4】求第 k 小的数

ycyy @ 2023-10-16 17:31:26


#include<bits/stdc++.h>
using namespace std;
int a[101];
void quicksort(int left,int right){
    int i,j,t,temp;
    if(left>right){
    return ;
    }
    temp=a[left];
    i=left;
    j=right;
    while(i!=j){
        while(a[j]>=temp&&i<j)j--;
        while(a[i]<=temp&&i<j)i++;
    if(i<j){
        t=a[i];
        a[i]=a[j];
        a[j]=t;
        }
    }
    a[left]=a[i];
    a[i]=temp;
    quicksort(left,i-1);
    quicksort(i+1,right);
}
int main(){
    int m,n;
    cin>>m>>n;
    for(int i=0;i<m;i++){
        cin>>a[i];
    }
    quicksort(0,m-1);
    cout<<a[n];
    return 0;
}

by Lyrith_with_xQ @ 2023-10-16 17:37:11

快排时间复杂度为 O(n \log n),本题数据 1\le n\le5000000n=5000000n \log n>10^8,会超时。


by 聊机 @ 2023-10-16 17:39:28

此题可以用快排思路达到O(n),常见trick自己看题解学。


by Terrible @ 2023-10-16 17:39:57

有没有可能你但凡是个完全排序都不能过?


by ycyy @ 2023-10-16 18:08:42

@Lyrith_with_xQ Ok谢谢


by ycyy @ 2023-10-16 18:09:00

@聊机 谢谢


by ycyy @ 2023-10-16 18:09:16

@Terrible 谢谢


by zhangbo1000 @ 2023-10-31 12:41:05

@Terrible 其实基数排序和桶排能过...


by Terrible @ 2023-10-31 12:54:13

@zhangbo1000 那再加一点,复杂度与元素值域无关的排序。[菜狗]


|