插入排序的几种形式

直接插入排序

直接插入排序是一种最简单的排序方法，他的操作是将后面的记录插入到已有的有序序列中。

举个栗子，有一串数字 1 4 2 9 3 8 6 7 5， 要从小到大排序

我们先把他们放进一个数组中，将数组的0号单元作为一个监视哨（当然也可以新开一个变量，可是作把0号单元作为监视哨有一个好处就是不用判断是否越界）

先看1和2，因为1、2号单元 已经有序，所以不用动

然后再看2，3。因为4>2，所以不可能有序，于是将2放入监视哨中

再找到2该插入的位置。插入位置往后的全部往后移一位

以此类推可以得到结果。

放上代码

template<typename T>
void Simple_Insert_Sort(T item[], size_t length) {
    for (int i = 2; i <= length; i++) {
        if (item[i - 1] > item[i]) {
            item[0] = item[i];
            item[i] = item[i - 1];
            int j;
            for (j = i - 2; item[0] < item[j]; j--) {
                item[j + 1] = item[j];
            }
            item[j + 1] = item[0];
        }
    }
}

我们可以发现，不管是查找还是移动，时间复杂度都是O(n^2)。我们可以寻求一些优化的方案。

折半插入排序

在n很小时可以考虑直接插入排序，当n很大时，很明显的搬家的次数过于多会导致整个程序的效率有所降低，那要找到一种方案来减小移动次数。

首先一种显而易见的方案就是将查找用折半查找，这样可以将查找的时间复杂度降到O(nlogn)，可是由于还设计到移动，移动的时间复杂度仍然是O(n^2)，故优化不大

2路插入排序

将折半查找的方式继续进行优化，由于一般来说，搬家会花费更多的时间，特别是被排序的对象比较大的时候，所以该如何减少移动次数？

2路插入排序就是想运用一块辅助储存空间，将被排序的组一分为二，选择插入在大的之后或者小的之前就可以减少一定的移动次数。

表插入排序

既然显而易见的是，移动比查找更加费时间，那为什么不使用链表的形式避免移动呢

首先来看

第一列是 data域，第二列是next域

其他方法与插入排序相同，但是将数据的插入变成指针的移动，减少了不必要的移动时间

void Linklist_Insert_Sort(int R[], int size) {
    int *next;
    next = new int[size];
    for (int i = 0; i < size - 1; i++) {
        next[i] = i + 1;
    }
    next[size - 1] = 0;
    int t = next[next[0]];
    next[next[0]] = 0;
    while (t) {
        int h = 0;
        int k = next[t];
        while (next[h] && (R[t] > R[next[h]])) {
            h = next[h];
        }
        next[t] = next[h];
        next[h] = t;
        t = k;
    }
    for (int i = 0; i < size; i++) {
        cout << next[i] << " ";
    }
    cout << endl;
    int i = 1;
    int j = next[0];
    while (i < size - 1) {
        if (i == j) {
            i++;
            j = next[j];
        }
        if (i < j) {
            int P = next[j];
            int temp = R[j];
            R[j] = R[i];
            R[i] = temp;
            next[j] = next[i];
            next[i] = j;
            i++;
            j = P;
        }
        if (i > j) {
            while (i > j)
                j = next[j];
        }
    }
}

希尔排序

最终的boss出场了。

希尔排序是插入排序当中最快的算法，其本质是通过使关键字基本有序来实现最小的移动次数。希尔排序将序列分成k个小的子序列，（k叫做希尔数），例如k=5，则子序列为

data[0],data[5] ;

data[1],data[6];

data[2],data[7];

data[3],data[8];

data[4],data[9];

先让每个子序列有序

然后减小k，如k=3，则心的子序列为

data[0],data[3],data[6],data[9];

data[1],data[4],data[7];

data[2],data[5],data[8];

保证每个子序列有序

再取k=1，使得整个序列有序

void Shell_insert(int data[],int dk, int length){
    for(int i=dk+1;i<=length; i++){
        if(data[i]>data[i+1]){
            data[0]=data[i];
            for(int j=i-dk;j>0&&(data[0]<data[j]);j-=dk){
                data[j+dk]=data[0];
            }
        }
    }
}

void Shell_Sort(int data[],int length, int shell[]){
    for(int i=0;i<length; i++){
        Shell_insert(data[],shell[i],length);
    }
}

希尔排序有着很神奇的时间复杂度，希尔排序的复杂度由希尔数决定，一般来说，希尔排序可以做到的最好时间复杂度是O(n^(3/2))。