这道题最后一个数据老超时，咋办？
ZZQ • 2年前
评论:
源码如下：
include<bits/stdc++.h>
using namespace std; int main() { int a[10005],n;//a为数组，n为数量 scanf("%d",&n);//读取n for(int i=1; i<=n; i++)
scanf("%d",&a[i]);//逐个读取排序元素
for(int j=1; j<=n-1; j++) { int flag=0;//定义flag，证明交换的次数 for(int i=1; i<=n-j; i++)
if(a[i]>a[i+1])
{
swap(a[i],a[i+1]);
flag++;
} if(flag==0)//如果没有交换过，则跳出循环
break;
}
for(int i=1; i<n; i++) printf("%d ",a[i]);//输出数组元素 printf("%d\n",a[n]); return 0; }
ZZQ • 2年前
100000的数据肯定得爆啊！ 你两个for循环时间就直接n²了，不能直接用冒泡，要么优化一下，要么就用其他的，要么就直接用sort。 我在下面给出几个排序的模板（改一下就行了）
wangjiajian • 2年前
插入排序模板 #include
using namespace std; int a[10]={10,9,8,7,6,5,4,3,2,1};
void Insert_Sort() {
int i=0;
int key=0;
int j=0;
for(i=1;i<10;i++)
{
key=a[i];
j=i-1;
while(j>=0&&key<a[j])//找到位置以后后移
{
a[j+1]=a[j];
j--;
}
a[j+1]=key;
}
}
int main() {
Insert_Sort();
for(int i=0;i<=9;i++)
cout<<a[i]<<" ";
return 0;
}
wangjiajian • 2年前
归并排序模板 #include using namespace std;
void merge(int arr[],int l,int mid,int r) {
//新建一个数组，复制arr中待合并的部分
int aux[r-l+1];
for(int m=l;m<=r;m++)
aux[m-l]=arr[m];
//i,j分别指向两个子数组的开头
int i=l,j=mid+1;
//开始合并
for(int k=l;k<=r;k++)
{
//哪一边先空了就直接把另一边复制过去
if(i>mid)
{
arr[k]=aux[j-l];
j++;
}
else if(j>r)
{
arr[k]=aux[i-l];
i++;
}
//两个子数组中哪个数字小就复制哪一个，然后对应的下标自增
else if(aux[i-l]<aux[j-l])
{
arr[k]=aux[i-l];
i++;
}
else
{
arr[k]=aux[j-l];
j++;
}
}
}
//归并排序，参数：数组名，左右区间 void merge_sort(int arr[],int l,int r) {
//递归出口，当划分到只有一个元素时，停止递归
if(l >=r)
return ;
int mid=(l+r)/2;
//递归分治左右
merge_sort(arr,l,mid);
merge_sort(arr,mid+1,r);
//将两个序列合并至一个
merge(arr,l,mid,r);
}
int main() {
int a[6];
for(int i=0;i<6;i++)
cin>>a[i];
merge_sort(a,0,5);
for(int i=0;i<6;i++)
{
cout<<a[i]<<" ";
}
return 0;
}
wangjiajian • 2年前
基数排序模板 #include
include
include
include
using namespace std; int a[10] = {73,22,93,43,55,14,28,65,39,81}; int n=10;
int getDigitNum(int x) {
if(x == 0) return 1;
int res = 0;
while(x){
res ++;
x /= 10;
}
return res;
}
void RadixSort() {
int mx = a[0];
for(int i = 1; i < n; i++)
if(mx < a[i]) mx= a[i];
//确定最大的位数
int maxNum = getDigitNum(mx);
int d = 1;
for(int k = 0; k < maxNum; k++)
{
vector<int> g[10];
for(int i = 0; i < 10; i++)
g[i].clear();
for(int i = 0; i < n; i++)
{
int tmp = a[i] / d % 10;
g[tmp].push_back(a[i]);
}
int cnt = 0;
for(int i = 0; i < 10; i++)
{
for(int j = 0; j < g[i].size(); j++)
a[cnt++] = g[i][j];
}
d *= 10;
}
} int main(){
RadixSort();
for(int i = 0; i < 10; i++)
printf("%d ", a[i]);
printf("\n");
return 0;
}
wangjiajian • 2年前
快速排序模板 \void quickSort(int a[],int L,int R){//快速排序-------------------------模板1
if(L>R) return;
int i=L,j=R;
int temp=a[L];//基准数为数组最左边的数
while(i!=j){
while(a[j]>=temp&&i<j)//先从右边开始找第一个小于基准数的数
j--;
while(a[i]<=temp&&i<j)//再从左往右找第一个大于基准数的数
i++;
if(i<j)//如果i和j没有相遇则交换他们
swap(a[i],a[j]);
}
swap(a[L],a[i]);//基准数归位
quickSort(a,L,i-1);//递归处理左边
quickSort(a,i+1,R);//递归处理右边
}
wangjiajian • 2年前
希尔排序模板 #include using namespace std; int a[10]={10,9,8,7,6,5,4,3,2,1};
void shell_sort() {
int j;
for (int gap = 10/2; gap > 0; gap /= 2)
{
for (int i = gap; i < 10; i++)
{
int temp = a[i];
for (j = i-gap; j >= 0 && temp < a[j]; j -= gap)
a[j+gap] = a[j];
a[j+gap] = temp;
}
}
}
int main() {
shell_sort();
for(int i=0;i<=9;i++)
cout<<a[i]<<" ";
return 0;
}
wangjiajian • 2年前
选择排序 /#include
include
using namespace std;
int main() {
int a[10];
int min;
int p,k;
for(int i=0;i<=9;i++)
cin>>a[i];
for(int i=0;i<=9;i++)
{
min=999999;
for(int j=i;j<=9;j++) //j从第i个位置开始找最小的
{
if(min>a[j])
{
min=a[j];
k=j;
}
}
//交换
p=a[k];
a[k]=a[i];
a[i]=p;
}
for(int i=0;i<=9;i++)
cout<<a[i]<<" ";
return 0;
}
wangjiajian • 2年前