插入排序：直接插入排序、折半插入排序、希尔排序的实现

直接插入排序

定义：直接插入排序是一种最简单的排序方法，其基本操作是将一条记录插入到已排好序的有序表中，从而得到一个新的、记录数量增 1 的有序表。

算法的代码：

#include <stdio.h>
#include <stdlib.h>


void print_series(const int series[], int len)
{
    for (int i = 0; i < len; i++)
    {
        printf("%d ", series[i]);
    }
    printf("\n");
}

void straight_insertion_sort(int s[], int len)
{
    for (int i = 1; i < len; i++)
    {
        int temp = s[i];
        int j;
        for (j = i - 1; j >= 0 && temp < s[j]; j--)
        {
            s[j+1] = s[j];
        }
        s[j + 1] = temp;
    }
}

int main(void)
{
    int series[] = {5, 7, 6, 8, 9, 2, 1, 4, 3};
    int len = sizeof(series) / sizeof(series[0]);

    // 排序前，打印
    printf("排序前，打印\n");
    print_series(series, len);

    // 排序
    straight_insertion_sort(series, len);
   
    // 排序后，打印
    printf("排序后，打印\n");
    print_series(series, len);

    return 0;
}

时间复杂度：\(O(n^2)\)

空间复杂度：\(O(1)\)

特点：

1）稳定排序
2）算法简便，且容易实现
3）即适用顺序存储结构，也适用链式存储结构，只是在单链表上无需移动记录，只需修改相应的指针

折半插入排序

定义：折半插入排序是直接插入排序的改进，通过在已经有序的序列（默认序列第一个元素为有序序列）中利用 二分查找 快速定位插入位置，这样经过n-1趟插入就能完成排序，当元素较多时，就平均性能来说，折半插入排序效率更优于直接插入排序

算法的代码：

#include <stdio.h>
#include <stdlib.h>


void print_series(const int series[], int len)
{
    for (int i = 0; i < len; i++)
    {
        printf("%d ", series[i]);
    }
    printf("\n");
}

void binary_insertion_sort(int s[], int len)
{
    for (int i = 1; i < len; i++)
    {
        int temp = s[i];
        int low = 0, high = i - 1;
        while (low <= high)
        {
            int m = (low + high) / 2;
            if (temp < s[m])
                high = m - 1;
            else
                low = m + 1;
        }
        for (int j = i - 1; j >= high + 1; j--)
        {
            s[j + 1] = s[j];
        }
        s[high + 1] = temp;
    }
}

int main(void)
{
    int series[] = {5, 7, 6, 8, 9, 2, 1, 4, 3};
    int len = sizeof(series) / sizeof(series[0]);

    // 排序前，打印
    printf("排序前，打印\n");
    print_series(series, len);

    // 排序
    binary_insertion_sort(series, len);
   
    // 排序后，打印
    printf("排序后，打印\n");
    print_series(series, len);

    return 0;
}

时间复杂度：\(O(n^2)\)

空间复杂度：\(O(1)\)

特点：
1）稳定排序
2）只适用于顺序存储结构
3）适合初始记录无序，n较大时的情况

希尔排序

定义：希尔排序是直接插入排序的改进，又称 "缩小增量排序"

算法的代码：

#include <stdio.h>
#include <stdlib.h>


void print_series(const int series[], int len)
{
    for (int i = 0; i < len; i++)
    {
        printf("%d ", series[i]);
    }
    printf("\n");
}

void shell_insert(int s[], int len, int i, int gap)
{
    for (int j = i + gap; j < len; j = j + gap)
    {
        if (s[j] < s[j - gap])
        {
            int temp = s[j];
            int k = j - gap;
            while (k >= 0 && s[k] > temp)
            {
                s[k + gap] = s[k];
                k = k - gap;
            }
            s[k + gap] = temp;
        }
    }
}

void shell_sort(int s[], int len)
{
    int gap; // 步长

    // 每一轮步长减半(也可采取其它步长方法)
    for (gap = len / 2; gap > 0; gap = gap / 2)
    {
        for (int i = 0; i < gap; i++)
            shell_insert(s, len, i, gap);
    }
}

int main(void)
{
    int series[] = {5, 7, 6, 8, 9, 2, 1, 4, 3};
    int len = sizeof(series) / sizeof(series[0]);

    // 排序前，打印
    printf("排序前，打印\n");
    print_series(series, len);

    // 排序
    shell_sort(series, len);
   
    // 排序后，打印
    printf("排序后，打印\n");
    print_series(series, len);

    return 0;
}

时间复杂度：当n -> 无穷大，\(On(log_2n)^2\)

空间复杂度：\(O(1)\)

特点：

1）记录跳跃式地移动导致排序不稳定
2）只适用顺序结构
3）增量序列gap可以有多种取法，但应该使增量序列中的值没有除1之外的公因子，并且最后一个增量值必须等于1
4）特别适用初始记录无序、n较大时的情况
5）当每轮循环中 gap = gap / 2 修改为 gap = gap - 1 ，算法就成了直接插入排序

参考引用

数据结构第二版：C语言版（严蔚敏）