离谱,离谱,真离谱
查看原帖
离谱,离谱,真离谱
759152
yinbe楼主2023/1/2 20:58

我手写的快排比插排和冒泡还快!!! 快排TLE3个,插排冒泡TLE各两个,有大佬能解释一下原因吗?

//快速排序
#include<iostream>
using namespace std;
int a[100001];
void qSort(int left,int right)
{
	if(left>right)
	{
		return;
	}
	int key=a[left],i=left,j=right;
	while(i<j)
	{
		while(i<j&&a[j]>=key)
		{
			j--;
		}
		a[i]=a[j];
		while(i<j&&a[i]<=key)
		{
			i++;
		}
		a[j]=a[i];
	}
	a[i]=key;
	qSort(left,j-1);
	qSort(j+1,right);
	return;
}
int main()
{
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
	}
	qSort(1,n);
	for(int i=1;i<=n;i++)
	{
		printf("%d ",a[i]);
	}
	return 0;
}
//插入排序
#include<iostream>
using namespace std;
int main()
{
	int n;
	scanf("%d",&n);
	int a[n+1],t;
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
	}
	for(int i=2;i<=n;i++)
	{
		t=a[i];
		int j; 
		for(j=i-1;j>=1&&a[j]>t;j--)
		{
			a[j+1]=a[j];
		}
		a[j+1]=t;
	}
	for(int i=1;i<=n;i++)
	{
		printf("%d ",a[i]);
	}
	return 0;
}
//冒泡排序
#include<iostream>
using namespace std;
int main()
{
	int n;
	scanf("%d",&n);
	int a[n+1],i,j;
	bool flag_swap;
	for(i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
	}
	for(i=1;i<=n-1;i++)
	{
		flag_swap=true;
		for(j=1;j<=n-i;j++)
		{
			if(a[j]>a[j+1])
			{
				swap(a[j],a[j+1]);
				flag_swap=false;
			}
		}
		if(flag_swap)
		{
			break;
		}
	}
	for(i=1;i<=n;i++)
	{
		printf("%d ",a[i]);
	}
	return 0;
}
2023/1/2 20:58
加载中...