直接插入排序

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

折半排序

void binary_search_sort()
{
    for(int i = 1; i < n; i ++)
    {
        if(a[i - 1] < a[i]) continue;
        int t = a[i], j = i;
        int l = 0, r = i - 1;//二分出第一个大于当前数的位置
        while(l < r)
        {
            int mid = l + r >> 1;
            if(a[mid] > t) r = mid;
            else l = mid + 1;
        }
        for(int j = i - 1; j >= r; j --)
            a[j + 1] = a[j];

        a[r] = t;

    }
}

冒泡排序

void bubble_sort()
{
    for(int i = 0; i < n - 1; i ++)
    {
        bool has_swap = false;//没有被交换过
        for(int j = n - 1; j > i; j --)//前i - 1已经有序， 从n-1到i， 只需要看到i + 1即可（相邻的连个元素）
        {
            if(a[j] < a[j - 1])
            {
                swap(a[j], a[j - 1]);
                has_swap = true;
            }
        }
        if(!has_swap) break;//如过没有被交换过说明已经有序
    }
}

选择排序

void select_sort()
{
    for(int i = 0; i < n - 1; i ++)
    {
        int k = i;//k记录的是后面最小数的位置
        for(int j = i + 1; j < n - 1; j ++)
        {
            if(a[j] < a[k]) k = j;
        }
        swap(a[i], a[k]);
    } 
}

希尔排序

void shell_sort()
{
    for(int d = n / 3; d; d = d == 2 ? 1 : d / 3)//d为公差，保证最后溢出d = 1;
    {
        for(int start = 0; start < d; start ++) 
        {
            for(int i = start + d; i < n; i += d)
            {
                int t = a[i], j = i;
                while(j > start && a[j - d] > t)
                {
                    a[j] = a[j - d];
                    j -= d;
                }
                a[j] = t;
            }
        }
    }
}