前言

一种将无序数组进行排序的方法。

插入排序，主要思想：每次提取一个元素插入到已排序的数组。
比如 [5 , 3, 4 ,1 ,2] 按从小到大的方式排序。
第一次：提取 3 插入到 5的左侧，列表变成 [3, 5, 4, 1, 2]
第二次：提取 4 插入到 5的左侧，列表变成 [3, 4, 5, 1, 2]
...

递归，主要思想：将任务转换为单一目的的循环，可以找到退出条件

递归插入排序，主要思想：每次递归插入一个元素，插完最后一个元素后退出递归。

接下来主要演示：普通直接插入排序、递归直接插入排序。

环境

编辑器：vs2019
文件：.c类型

正文

代码参考：

#include <stdio.h>


// 插入排序，主要思想：将元素插入到已排序的数组合适位置上。


// 普通直接插入排序，从小到大
int* insertion_sort_direct_normal(int source_array[], int source_array_length)
{
    for (int i = 1; i < source_array_length; i++)
    {
        int suit_index = i;

        // 找到合适的插入位置（若使用二分查找，则称之为二分插入排序）
        for (int j = 0; j < i; j++)
        {
            if (source_array[i] < source_array[j]) 
            {
                suit_index = j;
                break;
            }
        }

        // 移动数组，腾出位置，并赋值
        if (suit_index != i)
        {
            // 保留要移动的元素
            int tmp_value = source_array[i];
            // 腾出位置
            for (int k = i; k > suit_index; k--)
            {
                source_array[k] = source_array[k - 1];
            }
            // 赋值
            source_array[suit_index] = tmp_value;
        }
    }
    return source_array;
}


// 递归直接插入排序，从小到大
// 每次递归插入一个元素，通过loop_num退出递归。loop_num 初始值设为1。
int* insertion_sort_direct_recursive(int source_array[], int source_array_length, int loop_num)
{
    if (loop_num == source_array_length)
    {
        return source_array;
    }

    int suit_index = loop_num;

    // 找到合适的插入位置（若使用二分查找，则称之为二分插入排序）
    for (int j = 0; j < loop_num; j++)
    {
        if (source_array[loop_num] < source_array[j])
        {
            suit_index = j;
            break;
        }
    }

    // 移动数组，腾出位置，并赋值
    if (suit_index != loop_num)
    {
        // 保留要移动的元素
        int tmp_value = source_array[loop_num];
        // 腾出位置
        for (int k = loop_num; k > suit_index; k--)
        {
            source_array[k] = source_array[k - 1];
        }
        // 赋值
        source_array[suit_index] = tmp_value;
    }
    loop_num++;
    insertion_sort_direct_recursive(source_array, source_array_length, loop_num);
}


int* upset_array(int source_list[], int source_list_length)
{
    for (int i = 0; i < source_list_length; i++)
    {
        int rand_index = rand() % source_list_length;
        int tmp_value = source_list[i];
        source_list[i] = source_list[rand_index];
        source_list[rand_index] = tmp_value;
    }
    return source_list;
}


int main()
{
    // 生成随机测试列表
    int test_list[20];
    int test_list_length = sizeof(test_list) / sizeof(int);
    printf("测试列表： \n");
    for (int i = 0; i < test_list_length; i++)
    {
        test_list[i] = rand() % 100;
        printf("%d ", test_list[i]);
    }
    printf("\n");

    // 普通直接插入排序
    insertion_sort_direct_normal(test_list, test_list_length);
    printf("普通直接插入排序结果： \n");
    for (int i = 0; i < test_list_length; i++)
    {
        printf("%d ", test_list[i]);
    }
    printf("\n");

    // 打乱数组
    upset_array(test_list, test_list_length);
    printf("打乱测试列表： \n");
    for (int i = 0; i < test_list_length; i++)
    {
        printf("%d ", test_list[i]);
    }
    printf("\n");

    // 递归直接插入排序
    printf("递归直接插入排序结果： \n");
    insertion_sort_direct_recursive(test_list, test_list_length, 1);
    for (int i = 0; i < test_list_length; i++)
    {
        printf("%d ", test_list[i]);
    }
    printf("\n");

    return 0;
}

执行结果参考：

image.png

扩展

本文贴出的代码，在插入操作时，为了更直观的演示逻辑，而未选择更加精简的代码。在下一篇 希尔排序 时，也会用到插入操作，那里会使用精简的方法。

直观的插入操作逻辑：找到插入位置，然后将位置之后的元素向后移动一格，将元素插入。

精简的插入操作逻辑：由于被插入的序列已经是有序的，因此可以直接将当前元素依次与之前的元素做对比，若比之前元素小则将前面的元素后移，依次执行下去，直到找到合适的位置放下元素即可。此时查找合适的位置和移动元素是同时操作的。