插入排序（英语：Insertion Sort）是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

如果目标是把n个元素的序列升序排列，那么采用插入排序存在最好情况和最坏情况。最好情况就是，序列已经是升序排列了，在这种情况下，需要进行的比较操作需（n-1）次即可。最坏情况就是，序列是降序排列，那么此时需要进行的比较共有n(n-1)/2次。插入排序的赋值操作是比较操作的次数加上 (n-1）次。平均来说插入排序算法的时间复杂度为O(n^2）。因而，插入排序不适合对于数据量比较大的排序应用。但是，如果需要排序的数据量很小，例如，量级小于千，那么插入排序还是一个不错的选择。

插入排序算法描述：
1、从第一个元素开始，该元素可以认为已经被排序；
2、取出下一个元素，在已经排序的元素序列中从后向前扫描；
3、如果该元素（已排序）大于新元素，将该元素移到下一位置；
4、重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
5、将新元素插入到该位置后；
6、重复步骤2~5。

一、 插入排序源码

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

#define NUM 10

// 插入排序函数实现
void insertion_sort(int a[], int n)
{
	for(int i=1; i<n; i++)
	{
		int j, temp = a[i];
		
		for(j=i; j>0&&a[j-1]>temp; j--)
		{
			a[j] = a[j-1];
		}
		
		a[j] = temp;
	}
}

int main(void)
{
	int array[NUM];
	
	srand((unsigned int)time(NULL));
	
	// 给数组赋随机值
	for(int i=0; i<NUM; i++)
	{
		array[i] = rand()%100;
	}
	
	// 打印排序前数组
	for(int i=0; i<NUM; i++)
	{
		printf("%5d", array[i]);
	}
	
	printf("\n");
	
	// 插入排序
	insertion_sort(array, NUM);
	
	// 打印排序后数组
	for(int i=0; i<NUM; i++)
	{
		printf("%5d", array[i]);
	}
	
	printf("\n");
	
	return 0;
}

二、 运行结果

[root@fedora Workspace]# gcc insertion_sort.c -o insertion_sort -Wall
[root@fedora Workspace]# ./insertion_sort
   45   71   94   18   64   66    3   49   59   27
    3   18   27   45   49   59   64   66   71   94
[root@fedora Workspace]# ./insertion_sort
    3   86   38   58   40    2   62   76   86   66
    2    3   38   40   58   62   66   76   86   86
[root@fedora Workspace]# ./insertion_sort
   86   49   90   46   95    5    0   85   79   11
    0    5   11   46   49   79   85   86   90   95
[root@fedora Workspace]# ./insertion_sort
   42   79   69   68   57   88   15   54   76   35
   15   35   42   54   57   68   69   76   79   88
[root@fedora Workspace]# ./insertion_sort
   41   91   14   74   22    4   69    3   66   82
    3    4   14   22   41   66   69   74   82   91
[root@fedora Workspace]# ./insertion_sort
   95   40   78   72   96   59    5   37   34   42
    5   34   37   40   42   59   72   78   95   96