> 直接插入排序 有哨兵的存在

#include <iostream>

using namespace std;

const int N = 100010;

int q[N];

int insert_sort(int q[],int n)
{
    int i,j;
    for(i = 2;i <= n;i ++) //q[0] 作为哨兵存在 不存放任何元素 把每一个要插入的元素放到哨兵的位置
    {
        q[0] = q[i]; // 放到暂存位置 q[0] 既是暂存，也是哨兵

        for(j = i -1;q[0] < q[j];j --) //移动元素  
            q[j + 1] = q[j];
        q[j + 1] = q[0];      // 把暂存元素放到对应的位置 
    }
    return 0;
}

> 定义一个整数存放待插入元素用来代替哨兵，下标从一开始；

#include <iostream>

using namespace std;

const int N = 100010;

int q[N];

int insert_sort(int q[],int n)
{
    int i,j,s;
    for(i = 1;i < n;i ++)
    {
        s = q[i];

        for(j = i -1;j >= 0 && s < q[j];j --)
            q[j + 1] = q[j];
        q[j + 1] = s;
    }
    return 0;
}

折半插入排序依旧是O(n^2)

#include <iostream>

using namespace std;

const int N = 100010;

int q[N];

int insert_sort(int q[],int n)
{
    int i,j,low,high,mid,s;
    for(i = 1;i < n;i ++)
    {
        s = q[i];

        low = 0,high = i -1;

        while(low <= high)
        {
            mid = low + high >> 1;

            if (q[mid] > s) high = mid - 1;
            else low = mid + 1;
        }
        for(j = i -1;j >= low;j --)
            q[j + 1] = q[j];
        q[low] = s;
    }  
    return 0;
}

希尔排序

// 思想 ： 取增量 d, 每次缩小两个元素以d 为变量的位置

void ShellSort(int A[], int n)
{
    int dk, i, j;

    for (dk = n / 2; dk >= 1; dk = dk / 2)//步长变化
    {
        for (i = dk + 1; i <= n; ++i)//以dk为步长进行插入排序
        {
            if (A[i] < A[i - dk]) // 将A[i] 插入到有序增量子表
            {
                A[0] = A[i];     // 改变A[0] 的元素，并把较大的放入A[i]中
                for (j = i - dk; j > 0 && A[0] < A[j]; j = j - dk)
                    A[j + dk] = A[j];  //记录后移，查找插入的位置
                A[j + dk] = A[0];// 插入
            }
        }
    }
}