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;
    }
}

void binary_search_insert_sort()//折半插入排序
{
    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 >> 1;
            if(q[mid] > t) r = mid;
            else l = mid + 1;
        }
        for(int j = i - 1; j >= r; j --)
            q[j + 1] = q[j];
        q[r] = t;
    }
}

//冒泡
void bubble()
{
    for(int i = 0; i < n; i ++)
    {
        bool has_swap = false;
        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;
    }
}

//简单选择排序
void select_sort()
{
    for(int i = 0; i < n; i ++)
    {
        int k = i;
        for(int j = i + 1; j < n; j ++)
        {
            if(q[j] < q[k]) k = j;
        }
        swap(q[i], q[k]);
    }
}

//快排
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);
}

//归并排序
void merge_sort(int q[], int l, int r)
{
    if(l >= r) return;
    int mid = l + r >> 1;
    mergr_sort(q, l, mid);
    merge_sort(q, mid + 1, r);

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

    while(i <= mid) tmp[k ++] = q[i ++];
    while(j <= r) tmp[k ++] = q[j ++];

    for(int i = l; i <= r; i ++, j ++) q[i] = tmp[j];
}