题目描述
给出N个数,你的任务就是把这n个数从小到大排序^_^
输入
第一行一个整数,N(1<=n<=200000),表示有N个数 接下来有N行,每行一个数
输出
输出N行,表示已经排序的N个数
样例输入
5
2
3
1
4
5
样例输出
1
2
3
4
5
OJ:段错误,检查是否有数组越界,指针异常,访问到不应该访问的内存区域
代码:
#include
using namespace std;
int n,t;
int minn=1e9,maxn=-1e9;
int a[200005];
int main(){
cin>>n;
for(int i=1; i<=n; i++){
cin>>t;
a[t]++;
minn=min(minn,t);
maxn=max(maxn,t);
}
for(int i=minn; i<=maxn; i++){
for(int j=1; j<=a[i]; j++){
cout<" ";
}
}
return 0;
}
如果输入的数大于等于200005,则使用这个数作为下标访问数组a会数组越界;
从小到大排序,如果要求不高简单使用选择排序或冒泡排序即可,如果时间要求高可以使用希尔排序,下面的例子更改为使用希尔排序:
修改如下:
参考链接:
#include <bits/stdc++.h>
using namespace std;
int n,t;
int minn=1e9,maxn=-1e9;
int a[200005];
int main(){
cin>>n;
for(int i=0; i<n; i++){
// cin>>a[i];
// a[t]++;
// minn=min(minn,t);
//maxn=max(maxn,t);
cin>>a[i];
}
// https://blog.csdn.net/tjw316248269/article/details/105207710/
int size = n;
int gap = n;
int *arr=a;
while (gap > 1)
{
gap = gap / 3 + 1; //调整希尔增量
int i = 0;
for (i = 0; i < size - gap; i++) //从0遍历到size-gap-1
{
int end = i;
int temp = arr[end + gap];
while (end >= 0)
{
if (arr[end] > temp)
{
arr[end + gap] = arr[end];
end -= gap;
}
else
{
break;
}
}
arr[end + gap] = temp; //以 end+gap 作为插入位置
}
}
for(int i=0;i<n;i++){
cout<<a[i]<<endl;
}
return 0;
}
就没人回答吗