include[HTML_REMOVED]

using namespace std;
//快速排序nlog n,不稳定,空间log n
void quick_sort(int num[],int l,int r)
{
if(l>=r)
return ;
int i=l-1,j=r+1;
int mid=num[(l+r)>>1];
//int i=l-1,j=r+1;
//int mid=(i+r)>>1;

while(i<j)
{
    do i++;while(num[i]<mid);
    do j--;while(num[j]>mid);
    if(i<j) swap(num[i],num[j]);
}
quick_sort(num, l,j);
quick_sort(num,j+1,r);

}

//归并nlog n,稳定,空间 n
void merge_sort(int a[],int l, int r,int n)
{
if (l >= r) return;
int N=n;
int temp[N];
int mid = (l+r)>>1;
merge_sort(a,l, mid,n), merge_sort(a,mid+1, r,n);
int k = 0, i = l, j = mid+1;
while (i <= mid && j <= r)
{
if (a[i] < a[j]) temp[k ] = a[i ];
else temp[k ] = a[j ];

}
while (i <= mid) temp[k ++ ] = a[i ++ ];
while (j <= r) temp[k ++ ] = a[j ++ ];
for (int i = l, j = 0; i <= r; i ++ , j ++ ) a[i] = temp[j];

}
//选择排序n*n,不稳定,空间复杂度o1
void select_sort(int a[], int n)
{
for(int i=0;i[HTML_REMOVED]=0 && a[i]>key)
{
a[i+1] = a[i];
i–;
}
a[i+1] = key;
}

}
//冒泡排序nn,稳定,空间复杂度o1
void bubbleSort(int num[], int n)
{
for(int i=n-1;i>0;i–)
{
for(int j=0;j[HTML_REMOVED]num[j+1])
{
swap(num[j],num[j+1]);
}
}
}
}
//希尔排序nn和n*log n之间,稳定,空间复杂度o1
void shell_sort()
{
for (int gap = n >> 1; gap; gap >>= 1)
{
for (int i = gap; i < n; i )
{
int x = a[i];
int j;
for (j = i; j >= gap && a[j-gap] > x; j -= gap)
a[j] = a[j-gap];
a[j] = x;
}
}
}
int main()
{
int n;
cin>>n;
int num[n+1];
for(int i=0;i<n;i)
{
scanf(“%d”,&num[i]);
}
//quick_sort(num,0,n-1);
//merge_sort(num,0, n-1,n);
insert_sort(num, n);
for(int j=0;j<n;j++)
printf(“%d “,num[j]);
return 0;
}