蒟蒻求助为什么第一种的冒泡可以AC而第二种的快排却TLE?(指代码不同的地方)

回复帖子

@桜咲の日 2020-01-14 23:33 回复

//第一种:
#include<stdio.h>
#include<stdlib.h>
void quicksort(int *ptr,int left,int right)
{
    int i,j,temp,point;
    if(left>right)
    return;
    point=ptr[left];
    i=left;
    j=right;
    while(i!=j)
    {
        while(ptr[j]>=point && i<j)
        j--;
        while(ptr[i]<=point && i<j)
        i++;
        if(i<j)
        {
            temp=ptr[i];
            ptr[i]=ptr[j];
            ptr[j]=temp;
        }
    }       
    ptr[left]=ptr[i];
    ptr[i]=point;
    quicksort(ptr,left,i-1);
    quicksort(ptr,i+1,right);
}
int main()
{
    int n,sum=0,temp;
    int *ptr;
    scanf("%d",&n);
    ptr=(int *)malloc(sizeof(int)* n);
    for(int i=0;i<n;i++)
    scanf("%d",&ptr[i]);
    quicksort(ptr,0,n-1);
    if(n==1)
    printf("%d",ptr[0]);
     _else//(这里开始出现不同于第二种代码的地方)
    {
        for(int i=0;i<n-1;i++)
        {
            sum+=(ptr[i]+ptr[i+1]);
            ptr[i+1]+=ptr[i];
            for(int j=i+1;j<n-1;j++)
            {
                if(ptr[j]>ptr[j+1])
                {
                    temp=ptr[j];
                    ptr[j]=ptr[j+1];
                    ptr[j+1]=temp;
                }
                else
                break;
            }
        }
    }_ 
    printf("%d",sum);
    return 0;
}```
\\第二种:
#include<stdio.h>
#include<stdlib.h>
void quicksort(int *ptr,int left,int right)
{
    int i,j,temp,point;
    if(left>right)
    return;
    point=ptr[left];
    i=left;
    j=right;
    while(i!=j)
    {
        while(ptr[j]>=point && i<j)
        j--;
        while(ptr[i]<=point && i<j)
        i++;
        if(i<j)
        {
            temp=ptr[i];
            ptr[i]=ptr[j];
            ptr[j]=temp;
        }
    }       
    ptr[left]=ptr[i];
    ptr[i]=point;
    quicksort(ptr,left,i-1);
    quicksort(ptr,i+1,right);
}
int main()
{
    int n,sum=0,temp;
    int *ptr;
    scanf("%d",&n);
    ptr=(int *)malloc(sizeof(int)* n);
    for(int i=0;i<n;i++)
    scanf("%d",&ptr[i]);
    quicksort(ptr,0,n-1);
    if(n==1)
    printf("%d",ptr[0]);
    else//(这里开始是与第一段代码不一样的地方)
    {
        for(int i=0;i<n-1;i++)
        {
            sum+=ptr[i]+ptr[i+1];
            ptr[i+1]+=ptr[i];
            quicksort(ptr,i+1,n-1);
        }
    }
    printf("%d",sum);
    return 0;
}```
@lv_mao_da_lao  2020-01-15 08:01 回复 举报

这道题正解堆排 $O( n log n)$

冒泡 $O(n^2)$ 可以骗过去

快排 $O(n^2logn)$ 退化后更慢,死都过不去

反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。