#include <bits/stdc++.h>
using namespace std;

const int N = 100010;
int n,q[N];
int nn; // 大根堆的长度
int w[N];  // 堆、桶排序使用的辅助数组
int s[N]; // 桶排序使用的辅助数组

选择排序

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[i],q[k]);
    }

}

快速排序

int partition(int* a, int low, int high)
{
    int pivot = a[low];
    while(low < high)
    {
        while(low < high && a[high] >= pivot)
            high--;
        a[low] = a[high];
        while(low < high && a[low] <= pivot)
            low++;
        a[high] = a[low];
    }
    a[low] = pivot;
    return low;
}

void quicksort(int* a, int low, int high)
{
    if(low < high)
    {
        int part = partition(a,low,high);
        quicksort(a,low,part-1);
        quicksort(a,part+1,high);
    }

}

插入排序

void insertsort()
{
    for(int i = 1 ; i < n ; i++)
    {
       int t = q[i]; 
       int j = i;
       while(j && q[j-1] > t)
        {
            q[j] = q[j-1];
            j--;
        }
        q[j] = t;
    }
}

折半插入排序

void binary_sort_insert(){
    for(int i = 1 ; i < n ; i ++){
        if(q[i-1] <= q[i]) continue;
        int t = q[i]; //保存暂存元素
        int l = 0, r = i-1;
        while(l <= r){
            int mid = (l + r) / 2;
            if(q[mid] > t) r = mid - 1;
            else if(q[mid] <= t) l = mid + 1; //【注意】为了维持稳定性，让原本在前面的仍然在前面。所以默认当值相同时，让计算机当作“小”。
        }

        for(int j = i - 1; j >= l ; j --)
            q[j+1] = q[j]; 
        q[l] = t;
    }
}

归并排序

void shell_sort(){

    for(int d = n / 3 ; d ; d = d / 3)
    {
        for(int start = 0 ; start < d ; start++)
        {

            for(int i = start + d ; i < n ; i+= d)
            {
                int j = i, t = q[i];
                while(j && q[j-d] > t)
                {
                    q[j] = q[j-d];
                    j -= d;
                }
                q[j] = t;
            }
        }
    }
}

堆排序

void down(int i)    // i为需要维护的节点 , n为数组长度
{
    int largest = i;   // 默认父节点为最大
    int lson = 2 * i + 1;
    int rson = 2 * i + 2;

    if(lson < nn && q[largest] < q[lson])  largest = lson;
    if(rson < nn && q[largest] < q[rson])  largest = rson;

    if(largest != i)   // 如果发现父节点不是最大的
    {
        swap(q[i],q[largest]);
        down(largest);
    }
}

void heap(){
    nn = n;  //初始还没开始排序时，堆上的点数 = 全部点数。
    //建堆
    for(int i = (n-1-1)/2; i>= 0 ; i--)   // 从最后一个父节点开始遍历所以父节点，最后一个父节点为(n-1)/2。
        down(i);  // 遍历完所有循环之后，成功建成大根堆

    //排序
    for(int i = n - 1;i > 0 ; i--)
    {
        swap(q[i],q[0]);
        nn--;    // 排好一个，则堆上的点数减1
        down(0);
    }
}

归并排序

void merge(int l , int r){
    if(l >= r) return;
    int mid = (l + r) / 2;
    merge(l,mid);
    merge(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];
}

桶排序

void bucket_sort() // 桶排序
{
    for(int i = 0;   i < n ; i ++) s[q[i]] ++ ; // 用桶计数
    for(int i = 1;   i < N ; i ++) s[i] += s[i-1];
    for(int i = n-1; i >=0 ; i --) w[--s[q[i]]] = q[i];
    for(int i = 0 ;  i < n ; i ++) q[i] = w[i]; 

}

基数排序

void radix_sort(int d, int r) // 基数排序 ， d为位数，r为进制
{   
    int radix = 1;
    for(int i = 0; i < d ; i ++)
    {
        for(int j = 0 ; j < r ; j++) s[j] = 0;
        for(int j = 0 ; j < n ; j++) s[ q[j]/radix % r ]++;
        for(int j = 1 ; j <  r ; j++) s[j] += s[j-1];
        for(int j = n-1;j >= 0 ; j--) w[ --s[q[j]/radix % r]] = q[j];
        for(int j = 0;  j < n; j++) q[j] = w[j];
        radix *= 10;
    }
}

主函数调用

int main(){
    cin >> n;
    for(int i = 0 ; i < n;i++) cin >> q[i]; //读取

    // select_sort();
    // quicksort(q,0,n-1);
    // insertsort();
    binary_sort_insert();
    // shell_sort();
    // heap();
    // merge(0,n-1);
    // bucket_sort();
    // radix_sort(10,10);   // d为位数，r为进制


    for(int i = 0 ; i < n;i++) cout <<  q[i] <<' ';

    return 0;
}