对于少量元素的排序，插入排序是一个有效的算法。
一、概述
插入排序的工作方式就像许多人排序一手扑克牌。开始时，我们的左手为空并且桌子上的牌面向下（下一个元素未知）。然后我们每次从桌子上拿走（顶端的）一张牌并将它插入到左手中正确的位置。
为了找到一张牌的正确位置，我们从右到左将它与已经在手中的每张牌进行比较。拿在左手上的牌总是排序好的。
二、插入排序的实现
#include <stdio.h>
void insertionSort(int arr[],int n)
{
int i,j,key;
for(i=1;i<n;i++)
{
key = arr[i];
j=i-1;
while(j>=0 && arr[j]>key)
{
arr[j+1] = arr[j];
j = j-1;
}
arr[j+1] = key;
}
}上述代码为插入排序的C语言实现。
三、插入排序算法的分析
一般来说，算法需要的时间与输入的规模同步增长，如在考虑输入的情况下，排序1000个数需要比排序3个数更长的时间，所以我们通常把一个程序的运行时间描述成其输入规模的函数。
1）输入规模
输入规模的最佳概念依赖于研究的问题。对于许多问题，有时用两个数而不是一个数来描述输入规模可能更合适。
上述代码中我们直接给插入排序方法传入一个数组，不考虑输入规模的问题。
2）运行时间
一个算法在特定输入上的运行时间是指执行的进本操作数或步数。定义“步”的概念以便尽量独立于机器是方便的。
作为算法领域的初学者，笔者不做过多的数学分析 ，仅使用常见的初学者的分析观点：执行每行代码需要常数时间，虽然一行可能与另一行需要不同数量的时间；执行循环需要线性时间（一个循环可会执行N次）
3）时间复杂度分析
即使在对给定规模的输入（不考虑输入规模），一个算法的运行时间也可能依赖于给定的是该规模下的哪个输入。
对于插入排序，若输入的数组已经排好序，则出现最佳情况：
这时，当执行到 j=i-1 时，我们会发现有 arr[j]<key 。
这样就相当于内层循环不再执行循环体，而变成了一条单独的判断语句，内层循环的运行时间从线性级（O(n)）降为了常数级（O(1)。
由此，最佳情况下的插入排序只存在了一个循环体，因此该最佳情况的时间复杂度为线性级的，即时间复杂度为O(n)。
相反，若输入的数组为反向排序好的，则出现最坏情况：
这种情况下，我们每次都要执行内层循环，必须将每个元素arr[i]与整个已排序子数组arr[1..i-1]中的每个元素比较。
因此我们可以把最坏运行时间表示为an²+bn+c，是n的二次函数。
- an²：嵌套循环部分
- bn：外层循环与内层循环间的赋值语句 、内层循环的判断
- c： 外层循环与内层循环间的赋值语句 、内层循环的判断
因为在n很大的时候，低阶项的影响是很小的，所以我们忽略它对算法执行时间的影响，所以插入排序最坏情况运行时间复杂度为O(n²)