插入排序：将一个数据插入到一个已经排好序的有序数据序列中，从而得到一个新的、个数+1的有序数列；插入排序适用于少量数据排序，时间复杂度为O(n^2)。
实现思路：1.对于一个无序数组，选取第一个元素，看作一个有序数组
2.从第二个元素开始，插入到前面的有序数列
3.插入时，从有序数列的倒序开始，进行大小判断和位置调整，直至生成新的有序数列
4.算法实现如下（"扑克牌抓牌"时的排序方式就是“插入排序”）
//C语言实现
void insertionSort(int array[],int num)
{
//正序排列，从小到大
for (int i = ; i < num; i++)
{
int key = array[i];
int j = i;
while (j > && array[j - ] > key)
{
array[j] = array[j - ];//向有序数列插入时，如果大于key,则向后移动
j -- ;//位置向前移动判断下一个
}
array[j] = key;//找到了正确的位置
}
}
//Objective-C使用NSMutableArray的Category实现 //.h文件
@interface NSMutableArray (ArraySort) - (void)insertionSort; @end //.m文件
#import "NSMutableArray+ArraySort.h" @implementation NSMutableArray (ArraySort) - (void)insertionSort
{
for (int i = ; i < [self count]; i ++)
for (int j = i; j > ; j --)
if ([[self objectAtIndex:j - ] integerValue] > [[self objectAtIndex:j] integerValue])
[self exchangeObjectAtIndex:j withObjectAtIndex:j - ];
} @end
算法的时间复杂度
如果目标是把n个元素的序列升序排列，那么采用插入排序存在最好情况和最坏情况。
最好情况就是，序列已经是升序排列了，在这种情况下，需要进行的比较操作需（n-1）次即可。
最坏情况就是，序列是降序排列，那么此时需要进行的比较共有0 + 1 + 2+ ... + (n-1) = n(n-1)/2次。
平均来说插入排序算法的时间复杂度为O(n^2）。
因而，插入排序不适合对于数据量比较大的排序应用。但是，如果需要排序的数据量很小，例如，量级小于千，那么插入排序还是一个不错的选择。
稳定性
插入排序是在一个已经有序的小序列的基础上，一次插入一个元素。
当然，刚开始这个有序的小序列只有1个元素，就是第一个元素。
比较是从有序序列的末尾开始，也就是想要插入的元素和已经有序的最大者开始比起，如果比它大则直接插入在其后面，否则一直往前找直到找到它该插入的位置。
如果碰见一个和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。
所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，所以插入排序是稳定的。