作为简单排序中最重要的排序方法，插入排序和它的变型在几乎所有混合排序算法（如快速排序，归并排序，TIM排序）中起到了重要作用。今天我们就来看看插入排序的思想及实现。
 

一、算法思想

作为常用的排序，插入排序具有稳定性，适应性（有序数组的非退化）的好处，其中最常用的版本是直接插入排序，另一版本是是二分插入排序。这里我们先谈谈直接插入排序。

首先，插排是基于比较的排序，具有O(nlongn)的理论下界。而所谓的基于比较，就是通过比较数组中的元素，看谁大谁小，根据结果来调整元素的位置。因此，对于这类排序，就有两种基本的操作：①比较操作； ②交换操作

算法的基本思想是每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子序列中的适当位置，直到全部记录插入完成为止。其中，对于交换操作，可以优化成移动操作，即不直接进行两个元素的交换，还是用一个枢轴元素(tmp)将当前元素先保存起来，然后执行移动操作，待确定了最终位置后，再将当前元素放入合适的位置。有些排序算法，比较次数比较多，而移动次数比较少，而有些则相反。比如，归并排序和快速排序，前者移动次数比较多，而后者比较次数比较多。

二、算法步骤

插入排序的基本思想是在遍历数组的过程中，假设在序号 i （i>=1）之前的元素即 [0..i-1] 都已经排好序，本趟需要找到 i 对应的元素 x 的正确位置 k ，并且在寻找这个位置 k 的过程中逐个将比较过的元素往后移一位，为元素 x “腾位置”，最后将 k 对应的元素值赋为 x ，一般情况下，插入排序的时间复杂度和空间复杂度分别为O(n2) 和 O(1)。（通俗说法：把数组后面那些没排序的元素换到数组前面已经排好序的部分里对应的位置）

例如：45 80 48 40 22 78 

第一轮：45 [80] 48 40 22 78 ---> 45 80 48 40 22 78 i=1
第二轮：45 80 [48] 40 22 78 ---> 45 48 80 40 22 78 i=2
第三轮：45 48 80 [40] 22 78 ---> 40 45 48 80 22 78 i=3
第四轮：40 45 48 80 [22] 78 ---> 22 40 45 48 80 78 i=4
第五轮：22 40 45 48 80 [78] ---> 22 40 45 48 78 80 i=5
插入排序算法由N-1趟排序组成。初始时，只考虑数组下标0处的元素，只有一个元素，显然是有序的

第一趟 对下标 1 处的元素进行排序，保证数组[0,1]上的元素有序；

第二趟 对下标 2 处的元素进行排序，保证数组[0,2]上的元素有序；

..........

第N-1趟对下标 N-1 处的元素进行排序，保证数组[0,N-1]上的元素有序，也就是整个数组有序了。它的递归思想就体现在：当对位置 i 处的元素进行排序时，[0,i-1]上的元素一定是已经有序的了。

三、复杂度分析

这里的最坏的情况和平均情况从代码中就可以看出来，这个就是对于一个有序的序列来说，不需要进行交换，只是比较了n次，所以这里最好的时间复杂度就是O(n)。此外对于这个表，我是从另一篇博客里引用的，但是表中的空间复杂度有问题，原来为O(n)，但实际上因为插排所引用的只是一个tmp变量，所以复杂度应该是O(1)。

其实，插入排序的比较次数与数组的逆序数相关，因为插入排序在将某个元素插入到合适位置时消除这个元素的逆序数。由定理：N个互异数的数组的平均逆序数是 N(N-1)/4，可知：基于相邻元素之间的比较和交换的算法的时间复杂度的一个下界为O(N^2)
此外，还有另外一个高效的排序算法：希尔排序，采用了增量序列。因此，它可能获得一个更好的时间复杂度。比如，当希尔排序使用Hibbard增量序列时，它的最坏运行时间为O(N3/2)

四、算法实现

代码在VC++环境下编译通过

/*
  Insert排序数组测试：2018/03/17
  version: 直接插入排序
*/

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

#ifndef N
#define N 100
#endif // N

int arr[N];

inline int Insert_Sort( int *arr)
{
    register int i, j, tmp;
    int k;
    //int len = sizeof(arr);

    for(i = 1; i < N/10; i++)
    {
        printf("n");
        printf("The %dth times is: n", i);

        tmp = arr[i];
        j = i - 1;

        while( tmp < arr[j] && j >= 0)
        {
            arr[j + 1] = arr[j];
            j--;
        }

        arr[j + 1] = tmp;

        for(k = 0;k < N/10;k++)
        {
         printf("%2d |", arr[k]);
        }

    }
}


int main( int argc, int *argv[])
{
    int i;

    printf("please enter 10 numbers: n");

    for(i = 0;i < N/10;i++)
    {
        scanf("%d", &arr[i]);
    }

    Insert_Sort(arr);

    printf("n");
    printf("the ordered array is: n");

    for(i = 0;i < N/10;i++)
    {
        printf("%4d", arr[i]);

    }
}

输入：

5  11  23   7  8  42  9  10  6  3

输出：

最后

以上就是无奈黄蜂为你收集整理的有趣的算法（六）：3分钟看懂插入排序（C语言实现）一、算法思想二、算法步骤三、复杂度分析四、算法实现的全部内容，希望文章能够帮你解决有趣的算法（六）：3分钟看懂插入排序（C语言实现）一、算法思想二、算法步骤三、复杂度分析四、算法实现所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。