#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e6;
int n;
int q[N],si,w[N];
//直接插入排序
// 时间复杂度：
// 最好：O(n)
// 平均：O(n2)
// 最坏：O(n2)
// 空间复杂度：O(1)
//稳定，只会移动大的
void insert_sort()
{
    //从第二个开始
    for(int i=1;i<n;i++)
    {
        int t=q[i],j=i;//当前元素
        while(j&&q[j-1]>t)
        {
            q[j]=q[j-1];//前一个元素往后移动一位
            j--;
        }
        q[j]=t;
    }
}
// 折半插入排序
// 时间复杂度：
// 最好：O(n )
// 平均：O(n2)
// 最坏：O(n2)
// 空间复杂度：O(1)
//稳定，只会移动大的
void binary_search_insert_sort()
{
    for(int i=1;i<n;i++)
    {
        if(q[i-1]<=q[i])continue;//当前数不需要改变位置
        int t=q[i];
        //在0到i-1区间上二分出第一个比i大的数
        int l=0,r=i-1;
        while(l<r)
        {
            int mid=l+r>>1;
            if(q[mid]>t)r=mid;
            else l=mid+1;
        }
        //r到i-1向后移动一位
        for(int j=i-1;j>=l;j--)
        {
            q[j+1]=q[j];
        }
        q[l]=t;
    }
}
//冒泡排序
// 时间复杂度：
// 最好：O(n)
// 平均：O(n2)
// 最坏：O(n2) 有2分之n方个逆序对
// 空间复杂度：O(1)
// 稳定，相等不会交换
void bubble_sort()
{
    for(int i=0;i<n-1;i++)
    {
        bool  has_swap=false;
        //前i个元素已经排好序了，从i+1往后看
        for(int j=n-1;j>i;j--)
        {
            if(q[j]<q[j-1])
            {
                swap(q[j],q[j-1]);
                has_swap=true;
            }
        }
        if(!has_swap)break;//没有发生交换，说明已经有序
    }
}
//简单选择排序
// 时间复杂度：
// 最好：O(n2)
// 平均：O(n2)
// 最坏：O(n2) 有2分之n方个逆序对
// 空间复杂度：O(1)
// 不稳定 2 2 1 -> 1 2 2
void select_sort()
{
    for(int i=0;i<n-1;i++)
    {
        int k=i;//值最小的下标
        for(int j=i+1;j<n;j++)
        {
             if(q[j]<q[k])
             k=j;
        }
        swap(q[k],q[i]);
    }
}
//希尔排序
//插入排序对部分有序的序列效率很高
// 时间复杂度：(n^(3/2)
// 空间复杂度：O(1)
// 不稳定 分组导致 
void shell_sort()
{
    //枚举公差
    for(int d=n/2;d;d/=2)
    {
        for(int start=0;start<d;start++)
        {
            //做一次插入排序
            for(int i=start+d;i<n;i+=d)
            {
                int t=q[i],j=i;
                 while(j>start&&q[j-d]>t)
                {
                    q[j]=q[j-d];
                    j-=d;
                }
                q[j]=t;
            }
        }
    }
}
//快速排序（和王道不同,x不一定在分界点上，教材在分界点上）
// 时间复杂度：
// 最好：O(nlogn)分到中点
// 平均：O(nlogn)
// 最坏：O(n2)  
// 空间复杂度：O(logn)
// 不稳定 递归栈logn层
void quick_sort( int l, int r)
{
    if (l >= r) return;

    int i = l - 1, j = r + 1, x = q[l + r >> 1];
    while (i < j)
    {
        do i ++ ; while (q[i] < x);
        do j -- ; while (q[j] > x);
        if (i < j) swap(q[i], q[j]);
    }
    quick_sort(l, j), quick_sort(j + 1, r);
}

//

#include<iostream>
#include<algorithm>
using namespace std;
int poration(int *a,int low,int high)//用来每次找最中间的那个元素(分割元素)
{
    int mid=a[low];
    while(low<high)
    {
        while(low<high&&a[high]>=mid) high--;
        a[low]=a[high];
        while(low<high&&a[low]<=mid) low++;
        a[high]=a[low];
    }
    a[low]=mid;
    return low;
}
void quicksort(int *a,int low,int high)//主要进行递归的函数，用来进行快速排序，quicksort
{
    if(low<high)
    {
        int mid=poration(a,low,high);
        quicksort(a,low,mid-1);
        quicksort(a,mid+1,high);
    }
}
int main()
{
    int a[] = {1, 4, 2, 5, 7, 3, 2};
    int n=sizeof(a)/sizeof(int);
    quicksort(a,0,n-1);
    for(int i=0;i<n;i++)
    cout<<a[i]<<" ";
}

// 堆排序(完全二叉树，根>=儿子，顺序强于链式)
// 时间复杂度：
// 最好：O(nlogn)
// 平均：O(nlogn)
// 最坏：O(nlogn)  
// 空间复杂度：O(logn)
// 不稳定
void down(int u)
{
     int t=u;//当前值
     if(u*2<=si&&q[u*2]>q[t])t=u*2;
     if(u*2+1<=si&&q[u*2+1]>q[t])t=u*2+1;
     if(u!=t)
     {
         swap(q[u],q[t]);//交换根节点和子节点
         down(t);//递归
     }
}
void heap_sort()
{
    //下标一定从1开始
     si=n;//全局变量
    for(int i=n/2;i;i--)down(i);//从非叶子节点依次往上做建堆操作
    for(int i=0;i<n-1;i++)
    {
        swap(q[1],q[si]);
        si--;//删掉最后一个元素
        down(1);
    }
}
//归并排序
// 时间复杂度：
// 最好：O(nlogn)
// 平均：O(nlogn)
// 最坏：O(nlogn)  
// 空间复杂度：O(n)需要辅助数组和辅助栈
// 不稳定
void merge_sort(int l,int r)
{
    if(l>=r)return;//判断边界
    int mid=l+r>>1;
    merge_sort(l,mid);
    merge_sort(mid+1,r);
    //单层递归逻辑
    int i=l,j=mid+1,k=0;
    while(i<=mid&&j<=r)
    {
        //写等于号可以保证稳定性
        if(q[i]<=q[j])w[k++]=q[i++];
        else w[k++]=q[j++];
    }
    while(i<=mid)w[k++]=q[i++];
    while(j<=r)w[k++]=q[j++];
    for(i=l,j=0;j<k;i++,j++)q[i]=w[j];//辅助数组复制回原数组
}
int main() 
{
    cin>>n;
    for(int i=0;i<n;i++)cin>>q[i];
    // insert_sort;
    // binary_search_insert_sort();
    // bubble_sort();
    // select_sort();
    // shell_sort();
    // quick_sort(0,n-1);
    // heap_sort();
    // merge_sort(0,n-1);
    for(int i=0;i<n;i++)cout<<q[i]<<" ";
    return 0;
}