插入排序是所有排序方法中比较简单的一种算法，主要的实现思想是将数据按照一定顺序逐个插入到有序序列中，最终得到的序列就是已经排序好的数据。

插入排序算法可以对指定序列完成升序（从小到大）或者降序（从大到小）排序，对应的时间复杂度为 O(n2)。

更详细的讲，插入排序算法的实现思路是：初始状态下，将待排序序列中的第一个元素看作是有序的子序列。从第二个元素开始，在不破坏子序列有序的前提下，将后续的每个元素插入到子序列中的适当位置。

这里推荐一套非常 Nice 的数据结构和算法教程，教程以 C 语言作为开发语言，对各个知识点进行了图文并茂的讲解，还提供了完整、可运行的 C 语言程序，非常适合新手小白学习：

数据结构与算法教程，数据结构C语言版教程！这套数据结构与算法教程，基于C语言，适合初学者入门。数据结构教程最大的特点就是通俗易懂，以图文配合的方式讲解每个知识点，更有C语言完整代码和项目实践。https://xiexuewu.github.io/ds/举个简单的例子，用插入排序算法对 {14, 33, 27, 10, 35, 19, 42, 44} 实现升序排序的过程如下：

1) 将第一个元素 14 看作是一个有序的子序列 {14}，将剩余元素逐个插入到此序列的适当位置：

2) 将 33 插入到 {14} 中，由于 33 > 14，所以 33 应该插入到 14 的后面，新的有序序列变为 {14, 33}；

3) 将 27 插入到 {14, 33} 中，由于 27 < 33 同时 27 > 14，所以 27 应该插入到 14 和 33 的中间，新的有序序列变为 {14, 27, 33}；

4) 将 10 插入到 {14, 27, 33} 中，经过依次和 33、27、14 比较，最终断定 10 应该插入到 14 之前，新的有序序列变为 {10, 14, 27, 33}；

5) 将 35 插入到 {10, 14, 27, 33} 中，由于 35 > 33，所以 35 应该插入到 33 之后，新的有序序列变为 {10, 14, 27, 33, 35}；

6) 将 19 插入到 {10, 14, 27, 33, 35} 中，经过依次和 35、33、27、14 比较，最终断定 19 应该插入到 14 和 27 之间，新的有序序列变为 {10, 14, 19, 27, 33, 35}；

7) 将 42 插入到 {10, 14, 19, 27, 33, 35} 中，由于 42 > 35，所以 42 应插入到 35 之后，新的有序序列变为 {10, 14, 19, 27, 33, 35, 42}；

8) 将 44 插入到 {10, 14, 19, 27, 33, 35, 42} 中，由于 44 > 42，所以 44 应插入到 42 之后，新的有序序列变为 {10, 14, 19, 27, 33, 35, 42, 44}。

经过将各个待排序的元素插入到有序序列的适当位置，最终得到的就是一个包含所有元素的有序序列。

插入排序算法的C语言实现

结合伪代码，如下是用插入排序算法对 {14, 33, 27, 10, 35, 19, 42, 44} 实现升序排序的 C 语言程序：

#include <stdio.h>
#define MAX 8   //设定待排序序列中的元素个数
//list[MAX]为待排序序列
void insertion_sort(int list[MAX]) {
    int insert_elem;
    int position;
    int i;

    //从第 2 个元素（下标为 1）开始遍历
    for (i = 1; i < MAX; i++) {
        // 记录要插入的目标元素
        insert_elem = list[i];
        // 记录目标元素所在的位置，从此位置向前开始遍历
        position = i;

        // 从 position 向前遍历，找到目标元素的插入位置
        while (position > 0 && list[position - 1] > insert_elem) {
            //position 处的元素向后移动一个位置
            list[position] = list[position - 1];
            position--;
        }
        //将目标元素插入到指定的位置
        if (position != i) {
            list[position] = insert_elem;
        }
    }
}

int main() {
    int i;
    int list[MAX] = { 14, 33, 27, 10, 35, 19, 42, 44 };
    insertion_sort(list);
    //输出 list 数组中已排好序的序列
    for (i = 0; i < MAX; i++) {
        printf("%d ", list[i]);
    }
}

程序的输出结果均为：

10 14 19 27 33 35 42 44