#include<iostream>
#include <vector>
#include <cstdlib>
#include <cmath>
using namespace std;
//冒泡排序
void BubbleSort(int n,int *b)
{
for(int i = 0;i < n;i++)
{
for(int j = 0;j < n-i-1;j++)
{
if(b[j] > b[j+1])
{
int t = b[j];
b[j] = b[j+1];
b[j+1] = t;
}
}
}
}
//计数排序
int* CountingSort(int n,int* b)
{
int i,j;
int mi = b[0],ma = b[0];
for(i = 1;i < n;i++)
{
if(b[i] < mi)
mi = b[i];
if(b[i] > ma)
ma = b[i];
}
int* count = (int*)malloc((ma-mi+1)*sizeof(int));
for(int i = 0;i < n;i++)
count[b[i] - mi]++;
for(int i = 0,j = 0;i < ma-mi+1;i++)
{
while(count[i])
{
b[j] = i + mi;
count[i]--;
j++;
}
}
free(count);
count = NULL;
return b;
}
void HeapAdjust(int *A,int s,int m)
//已知A[s,...,m]中记录的关键字除A[s]之外均满足堆的定义，本函数调整A[s]
//的关键字，使A[s,...,m]成为一个大顶堆(对其中记录的关键字而言)
{
int j,rc=A[s];
for(j=2*s+1;j<=m;j=2*j+1)
{
if(j<m&&A[j]<A[j+1])
j++;
if(rc>A[j])
break;
A[s]=A[j];
s=j;
}
A[s]=rc;
}
//堆排序
int* HeapSort(int n,int* b)
{
int i,temp;
for(i=n/2-1;i>=0;--i)
HeapAdjust(b,i,n-1);
for(i=n-1;i>0;i--)
{
temp=b[0];
b[0]=b[i];
b[i]=temp;
HeapAdjust(b,0,i-1);
}
return b;
}
//插入排序
int* InsertionSort(int n,int* b)
{
int i=1,j,temp;
while(i<n)
{
temp=b[i];
j=i-1;
while(j>=0&&b[j]>temp)
{
b[j+1]=b[j];
j--;
}
b[j+1]=temp;
i++;
}
return b;
}
void Merge(int *A,int *B,int i,int m,int n)
//将有序的A[i,...,m]和A[m+1，...,n]归并为有序的B[i,...,n]
{
int j,k;
for(j=m+1,k=i;i<=m&&j<=n;k++)
{
if(A[i]<A[j])
B[k]=A[i++];
else
B[k]=A[j++];
}
if(i<=m)
while(i<=m)
B[k++]=A[i++];
if(j<=n)
while(j<=n)
B[k++]=A[j++];
}
void Msort(int *A,int *B,int s,int t)
//将A[s,...,t]归并排序为B[s,...,t]
{
if(s==t)
B[s]=A[s];
else
{
int m=(s+t)/2;
int C[100]={0};
Msort(A,C,s,m);
Msort(A,C,m+1,t);
Merge(C,B,s,m,t);
}
}
int* MergeSort(int n, int* b)
//归并排序
{
Msort(b,b,0,n-1);
return b;
}
void quick_sort(int s[], int l, int r)
{
if (l < r)
{
//Swap(s[l], s[(l + r) / 2]); //将中间的这个数和第一个数交换 参见注1
int i = l, j = r, x = s[l];
while (i < j)
{
while(i < j && s[j] >= x) // 从右向左找第一个小于x的数
j--;
if(i < j)
s[i++] = s[j];
while(i < j && s[i] < x) // 从左向右找第一个大于等于x的数
i++;
if(i < j)
s[j--] = s[i];
}
s[i] = x;
quick_sort(s, l, i - 1); // 递归调用
quick_sort(s, i + 1, r);
}
}
//选择排序
void SelectionSort(int n,int* b)
{
for(int i = 0;i < n-1;i++)
{
int mi = i;
for(int j = i+1;j < n;j++)
{
if(b[j] < b[mi])
mi = j;
}
if(mi != i)
{
int t = b[i];
b[i] = b[mi];
b[mi] = t;
}
}
}
//希尔排序
int* ShellSort(int n, int* A)
//Ï£¶ûÅÅÐò
{
int gap,i,j,temp;
if(n==1)
return A;
for(gap=n/2;gap>0;gap/=2)
{
i=gap;
while(i<n)
{
temp=A[i];
j=i-gap;
while(j>=0&&A[j]>temp)
{
A[j+gap]=A[j];
j=j-gap;
}
A[j+gap]=temp;
i++;
}
}
return A;
}
int main()
{
int n;
cin >> n;
int b[n];
for(int i = 0;i < n;i++)
{
cin >> b[i];
}
//BubbleSort(n,b);
//CountingSort(n,b);
//HeapSort(n,b);
//InsertionSort(n,b);
//MergeSort(n,b);
//quick_sort(b,0,n-1);
//SelectionSort(n,b);
//ShellSort(n,b);
for(int i = 0;i < n;i++)
{
cout << b[i] << " ";
}
cout << endl;
return 0;
}
