#include <iostream>

using namespace std;

int n;
int a[100];

/*
插入排序
空间复杂度：O(1),只有t这个中间变量，不计算输入规模n
时间复杂度：O(n^2)
稳定性：稳定
*/
void insertSort(int a[]) {
    for(int i=1; i<n; i++) {
        int t = a[i];  //待排序的第一个元素
        int j;  //记录有序数组的指针
        for(j = i-1; j>=0; j--) {
            if(a[j] > t) a[j+1] = a[j];  //如果该元素大于t，则将该元素移到下一位
            else break;  //此时a[j]<=t，t因该插入到j的后面，退出循环
        }
        a[j+1] = t;  //此时a[j]<=t，，也保证了稳定性
    }
}

/*
选择排序
空间复杂度：O(1)
时间复杂度：O(n^2)
稳定性：不稳定
比如说：5，8，5，2，9 这样一组数据，使用选择排序算法来排序的话，
第一次找到最小元素 2，与第一个 5 交换位置，那第一个 5 和中间的 5 顺序就变了，所以就不稳定了。
正是因此，相对于冒泡排序和插入排序，选择排序就稍微逊色了。
*/
void selectSort(int a[]) {
    for(int i=0; i<n; i++) {
        int min = i;  //当前最小的元素的下标初始化为待排序的第一个元素下标
        for(int j=i+1; j<n; j++) {
            if(a[j] < a[i]) {
                min = j; //更新元素序列的最小值下标
            }
        }
        int t = a[min];  //将选择出的最小元素进行交换
        a[min] = a[i];
        a[i] = t;
    }
}

/*
快速排序
空间复杂度：O(nlogn)，递归调用栈
时间复杂度：O(nlogn)
稳定性：不稳定
*/
void quick_sort(int q[],int l,int r)
{
    if(l>=r) return;
    int x=q[(l+r)>>1],i=l-1,j=r+1;
    while(i<j)
    {
        /*
            要保证指针能往下走所以要先++再判断，例如q[i]=q[j]=x时，交换i,j后仍然不满足while，指针就不会移动
            while(q[i] < x) i++;
            while(q[j] > x) j--;
            if(i<j) swap(q[i],q[j]);
        */
        do i++; while(q[i]<x);
        do j--; while(q[j]>x);
        if(i<j) swap(q[i],q[j]);
    }

    quick_sort(q,l,j);

    quick_sort(q,j+1,r);
}


/*
希尔排序，只能使用顺序表
空间复杂度：O(1)
时间复杂度：O(nlogn)
稳定性：不稳定
*/
void shellSort(int a[]) {
    int gap = n;  //下标从0开始，gap/2就是第一组的第二个元素下标
    while(gap>0) {
        gap/=2;
        for(int i=gap; i<n;i++) {
            int t = a[i];
            int j; //因为是i++，所以每次循环的j都会切换不同子序列
            // 在当前子序列中进行插入排序
            for(j=i-gap; j>=0; j-=gap) {
                if(a[j] > t) a[j+gap] = a[j];
                else break;
            }
            a[j+gap] = t;
        }
    }
}

/*
冒泡排序，可以适用于链表
空间复杂度：O(1)
时间复杂度：O(n^2)
稳定性：稳定
*/
void bubbleSort(int a[]) {
    int f = 1;
    for(int i=1; i<n; i++) {
        for(int j=0; j<n-i; j++) {
            if(a[j] > a[j+1]) {  //确保了稳定性
                int t = a[j];
                a[j] = a[j+1];
                a[j+1] = t;
                f = 0;
            }
        }
        if(f) break;
    }
}
/*
归并排序
空间复杂度：O(n)，递归调用栈
时间复杂度：O(nlogn)
稳定性：稳定
*/
void merage_sort(int a[],int l,int r) {
    if(l >= r) return;
    int mid = (l+r)>>1;

    merage_sort(a,l,mid);
    merage_sort(a,mid+1,r);

    int i = l,j = mid+1,k = 0;
    int t[r-l+1];
    while(i<=mid && j<=r) {
        if(a[i] <= a[j]) t[k++] = a[i++];
        else t[k++] = a[j++];
    }
    while(i<=mid) t[k++] = a[i++];
    while(j<=r) t[k++] = a[j++];

    //l，r的元素排序好之后是在一个临时数组里，这就是把临时数组中的元素复制到目标数组
    //因为前面说明了，我们排序的数组的区间是[l , r ]，那么吧这段区间内的数字排序好以后还是只能放在这段区间里面的
    for(int i=l,k=0; i<=r; i++,k++) a[i] = t[k];
}

/*
堆排序
空间复杂度：O(n^2)
时间复杂度：O(nlogn)
稳定性：不稳定
*/


int main() {
    cin >> n;
    for(int i=0; i<n; i++) cin >> a[i];
    bubbleSort(a);
    for(int i=0; i<n; i++) cout << a[i] << " ";

    return 0;
}