Воспользуйтесь
магической силой сортировки подсчётом и отсортируйте n чисел из диапазона [0; 100000].
Вход. Первая строка содержит число n (1 ≤ n ≤ 106). Далее идут n чисел, которые следует отсортировать.
Выход. Выведите n отсортированных
чисел.
|
Пример входа |
Пример выхода |
|
3 2 3 1 |
1 2 3 |
сортировка
Входные числа
можно отсортировать методом подсчета, так как они целые и нам известен их
диапазон.
Входные числа
храним в массиве m.
#define MAX 100010
int
m[MAX];
Читаем входные данные.
В m[i] подсчитываем сколько раз
встретилось число i среди заданных.
scanf("%d",&n);
memset(m,0,sizeof(m));
for(i = 0; i < n; i++)
{
scanf("%d",&v);
m[v]++;
}
Выводим полученный массив. Число i выводим m[i] раз.
for(i = 0; i < MAX; i++)
for(j = 0; j
< m[i]; j++)
printf("%d
",i);
printf("\n");
#include <cstdio>
#include <vector>
using namespace std;
vector<int> v;
int
n, i;
vector<int> sort(vector<int>
&a)
{
int i, len =
a.size();
vector<int>
c(100001), b(len);
for(i = 0; i
< len; i++) c[a[i]]++;
for(i = 1; i
< 100001; i++) c[i] += c[i-1];
for(i = 0; i
< len; i++)
b[--c[a[i]]] = a[i];
return b;
}
int
main(void)
{
scanf("%d",&n);
v.resize(n);
for(i = 0; i
< n; i++)
scanf("%d",&v[i]);
v = sort(v);
for(i = 0; i
< v.size(); i++)
printf("%d
",v[i]);
printf("\n");
return 0;
}
Java реализация
import java.util.*;
public class Main
{
static int MAX = 100001;
public static void main(String[] args)
{
Scanner con = new Scanner(System.in);
int n = con.nextInt();
int m[] = new int[MAX];
for(int i = 0; i < n; i++)
{
int v = con.nextInt();
m[v]++;
}
for(int i = 0; i < MAX; i++)
for(int j = 0; j < m[i]; j++)
System.out.print(i + " ");
System.out.println();
con.close();
}
}