C语言必学的12个排序算法：直接插入排序（第1篇）

Bertha 。 2023-03-03 15:29 3阅读 0赞

# 为什么学习排序算法 #

排序和查找是计算机专业课程数据结构和算法中最重要的部分之一，也是编程中常用的基础知识。C语言初学者对直接插入、简单选择两种最简单的排序算法必须掌握，足以应付一般的考试、课程设计、小程序编写。

但是对于计算机专业、编程开发的同学，必须熟练掌握这12个算法，达到手写算法的程序，排序算法在算法能力训练、考研笔试和机试、工作面试、真实软件项目中普遍使用。

C语言必须的12个排序算法文章系列，每篇文章介绍一个算法，使用C语言实现一个排序算法，这些代码可以作为模板代码，大家可以收藏，方便编程使用。

备注：所有排序算法程序，默认均为从小到大排序，至于从大到小，可以简单修改比较方式即可实现。另外所有程序都是独立可运行的完整C语言程序，而不仅仅知识给出一个函数或伪代码。

# 直接插入排序算法基本思想 #

每次循环，将当前的一个记录插入到之前已经插入排序好的有序子表中，从而得到一个新的、记录数增加1的有序子表。

例如：给定10个整数：(4,3,1,2,6,5,0,9,8,7) 从小到大排序。

*  首先排序第1个数据 4，因为此时只有一个数据，无需排序，肯定有序，得到有序子表(4)；
 *  再看第2个数据 3，和之前4发现小，因此需要插入到4前面，首先将4向后移动占用1的位置，空出位置将3插入到原来4的位置，得到有序子表(3,4)；
 *  第3个数据 1， 依次和有序子表(3,4)比较，发现小于它们，因此将4后移位置占用1的位置，将3也后移，将1直接插入到原来3的位置，得到(1,3,4)；
 *  …依次循环，完成10个整数排序。

很明显，每次只处理一个数据，每次数据比较后，移动前面数据的位置，插入到合适位置。

直接插入算法时间复杂度是O(n^2)，需要一个记录大小的辅助空间，算法是稳定的排序。

# 代码实现 #

读代码是最精确的学习方式，建议大家多读。

第一种方式：

/*
    #include <stdio.h>
    void insert_sort(int a[], int length)
    {
    int i,j;
    int t;
    for(i=1; i<length; i++)
    {
    if(a[i] < a[i-1] )
    {
    t = a[i];
    a[i] = a[i-1];
    for(j=i-2; j>=0 && t < a[j]; j--)
    a[j+1] = a[j];
    a[j+1] = t;
    }
    }
    }
    int main(void)
    {
        int a[10] = {4,3,1,2,6,5,0,9,8,7};
        insert_sort(a,10);
        int i;
        for(i=0; i<10; i++)
          printf("%d ", a[i]);
        return 0;
    }

很明显，insert\_sort函数中，需要临时变量t保存待排数据记录，因此需要一个辅助空间，两层循环，时间复杂度是O(n^2)

第二种方式：在保存数据记录的数组中，增加一个空间a\[0\]，用作监视哨，a\[0\]单元作为辅助空间，这样不需要临时变量t，也不需要判断 j>=0防止数组下标出界。这是很精巧的设计，很多教材中均有介绍。

/*
    #include <stdio.h>
    // a[0]临时辅助空间，数据从a[1]开始 
    void insert_sort(int a[], int length)
    {
    int i,j;
    for(i=2; i<=length; i++)
    {
    if(a[i] < a[i-1] )
    {
    a[0] = a[i];
    a[i] = a[i-1];
    for(j=i-2; a[0] < a[j]; j--)
    a[j+1] = a[j];
    a[j+1] = a[0];
    }
    }
    }
    int main(void)
    {
    // a[0] 不保存数据 
        int a[11] = {0,4,3,1,2,6,5,0,9,8,7};
        insert_sort(a,10);
        int i;
        for(i=1; i<=10; i++)
          printf("%d ", a[i]);
        return 0;
    }

其实做为一个学习者，有一个学习的氛围跟一个交流圈子特别重要这里我推荐一个C/C++基础交流583650410，不管你是小白还是转行人士欢迎入驻，大家一起交流成长。  
![format_png][]  
![format_png 1][]

[format_png]: /images/20230208/c8f9bc510b0741bda840c59322a515ac.png
[format_png 1]: /images/20230208/249164941af744288b75b5dfc6bc91d6.png