插入排序

1、直接插入排序(Straight Insertion Sort)

(1)描述

将一个无序区的数据插入到已排好的有序表中的恰当位置，得到一个新的有序表。

和打扑克牌很类似，从盖住的无序牌中摸一张牌，插入到手里的有序牌中适当的位置，使手里的牌依然保持有序。

(2)实现

外层循环i表示待插入的数据的下标，在i之前的是有序部分，
k用于遍历i-1到0，从中找到合适的位置让新数据插入。

void straight_insertion(int data[], int length)
{
    int i, k;
    int temp;
    for (i = 1; i < length; ++i)
    {
        temp = data[i];
        for (k = i-1; k >= 0 && data[k] > temp; --k)
        {
            data[k+1] = data[k];
        }
        data[k+1] = temp;
    }
}

代码链接
链表版

(3) 时间复杂度 O(n²)

找到合适的插入位置需要与前面的元素挨个比较，时间复杂度是O(n)，一共需要插入 n-1 次，所以是 O(n²) 。

如果优化成二分插入排序，虽然找合适的插入位置比较快，但是找到插入位置之后，数据还是要一个一个往后挪，整体的复杂度并没有改变。

最好情况，也就是在已经有序的情况下，时间复杂度是O(n)。

(4)空间复杂度 O(1)

(5)稳定性：稳定

2、希尔排序(Shell's Sort)

(1)描述

又称“缩小增量排序”(Diminishing Increment Sort)，是一种分组插入的排序。

设有 n 个数据，先取一个整数 increment (小于n)作为增量，把待测数据分为 increment 个子集，距离为 increment 的元素放在同一个小组中，在每组分别进行直接插入排序。然后缩小增量 increment ，重复上述过程。直到 increment=1 ，所有元素在同一个分组中已经基本有序，再进行最后一次排序就完成了。

因为直接插入排序每次只能将数据移动1位，插入1个数据得把很多数据往后移动，效率较低；
希尔排序每次交换的是一定间隔的数据，刚开始时每组只有很少数据，所以排序很快，之后每组的数据越来越多，但这些数也越来越有序，所以排序速度也较快。

增量的选择会直接影响到希尔排序的性能，不过只要最终 increment 是1都可以正确排序。

有以下几种增量选择：
希尔增量序列 {N/2, (N / 2)/2, ..., 1}
Hibbard增量序列 {1, 3, ..., 2^k-1}
Sedgewick增量序列 {1, 5, 19, 41, 109...}，该序列中的项或者是9 * 4 ⁱ - 9 * 2 ⁱ + 1 或者是 4 ⁱ - 3 * 2 ⁱ + 1

(2)实现

与直接插入排序相比，希尔排序增加了一层循环，用于控制 increment 变化。

void diminishing_increment(int data[], int length)
{
    int i, k;
    int increment;
    int temp;

    for (increment = length / 2; increment >= 1; increment/=2)
    {
        for (i = increment; i < length ; ++i)
        {
            temp = data[i];
            for (k = i-increment; k >= 0 && data[k] > temp; k-=increment)
            {
                data[k+increment] = data[k];
            }
            data[k+increment] = temp;
        }
    }
}

代码链接

(3) 时间复杂度

时间复杂度依赖于增量序列函数的选择。
希尔的时间复杂度比较模糊，据说约为O(n^1.3)，
最坏的情况下希尔排序的时间复杂度为O(n^2)，下面取希尔增量序列{n/2, (n / 2)/2, ..., 1}，计算最坏的情况：

• 第1次增量是n/2，每组有2个数据，比较 1 次，n/2轮，

• 第2次增量是n/4（n/2/2不一定等于n/4，这里取约等于），每组有4个数据，最多比较 (1+2+3) 次，n/4轮，（第4个数据与前3个相比，第3个数据与前2个相比，第2个数据与第1个比，最差情况一共是3+2+1次比较），

• 第3次增量是n/8，每组有8个数据，最多比较 (1+2+...+7) 次，n/8轮，

• 第x次增量是n/1，每组有2^x个数据，最多比较 (1 + 2 + ... + (2 ^x -1) ) 次，1轮，

• 设一共有m次，即x的最大值是m，则 2 ^m <= n < 2 ^m+1
  比如：
  当n=16，则m=4，属于 2 ^m = n
  当n=32，则m=5，属于 2 ^m = n
  当n=20，则m=4，属于 2 ^m < n < 2 ^m+1

设 a_x 为第 x 次需要比较的次数， S_x 为前x项的和。则：

所以最坏时间复杂度是 O(n ²)

(4)空间复杂度 O(1)

(5)稳定性：不稳定