插入排序基本概念

插入排序，一般也被称为直接插入排序。对于少量元素的排序，它是一个有效的算法。排序思想是将无序子序列中的一个或几个记录“插入”到有序子序列中，从而增加有序子序列的长度。

算法步骤解析

1. 从数组的第二个数据开始往前比较（这里将数组的第一个元素当成一个有序序列），即一开始用第二个数和它前面的一个比较，如果符合条件（比前面的大或者小），则让他们交换位置。
2. 然后再用第三个数和第二个比较，符合则交换，但是此处还得继续往前比较，（比如有 4个数3，15，18，45, 17,17比45小，需要交换，但是17也比20小，也要交换），当不需 要和15交换以后，说明也不需要和15前面的数据比较了，肯定不需要交换，因为前面的数据都是有序的肯定都比15还要小。
3. 重复步骤二，直到数据全都排完。

上图表示了插入排序的流程图及动态排序过程，方便大家理解插入排序的过程

代码实例

#include <stdio.h>
void insertion_sort(int arr[], int len){
    int i,j,temp;
    for (i=1;i<len;i++){ // i从1开始，将arr[0]当成一个有序的序列 
            temp = arr[i]; // 将要插入的数据 
            for (j=i;j>0 && arr[j-1]>temp;j--) // 比较待插入数据域有序序列的大小 
                    arr[j] = arr[j-1]; // 将比插入数据大的数据依次后移 
            arr[j] = temp; // 将待插入的数据temp插入到对应的位置 
    }
}

int main() {
    int arr[] = { 22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70 };
    int len = (int) sizeof(arr) / sizeof(&arr[0]);
    insertion_sort(arr, len);
    int i;
    for (i = 0; i < len; i++)
        printf("%d ", arr[i]);
    printf("\n");
    return 0;
}

代码解析：

1. 第4行的for循环用来遍历待排序的数据
2. 第6，7行将待排序的数据与前面已排序的数据进行比较，并将比插入数据大的数据依次后移
3. 第8行将待插入的数据temp插入到对应的位置

执行结果如下：

算法性能

属于稳定的排序，适合于数据量小，部分数据有序的情况排序。

如果目标是把n个元素的序列排列，采用插入排序存在最好情况和最坏情况。

• 在插入排序中，当待排序数组是有序时，是最优的情况。只需当前数跟前一个数比较一下就可以了，这时一共需要比较N- 1次，时间复杂度为O(N)
• 最坏情况就是，序列是降序排列，那么此时需要进行的比较共有n(n-1)/2次。时间复杂度为O(N^2)

平均来说插入排序算法的时间复杂度为O(N^2)。

因而，插入排序不适合对于数据量比较大的排序应用。但是，如果需要排序的数据量很小，例如，量级小于千，那么插入排序还是一个不错的选择