首先了解两个概念：
1. 内排序和外排序
内排序，参加排序的数据量不大，在排序过程中可以将所有参加排序的数据存放在内存中处理的排序方法。
外排序，参加排序的数据量很大，以至于内存不足以一次存放全部数据，在排序过程中需要通过内存与外存之间的数据交换来达到排序目的的排序方法。
2. 稳定性排序与非稳定性排序
参加排序的项称为排序码或者排序项。
这个概念是针对的是有多个相同的排序项参加排序的情况。若采用排序方法排序后这些相同的排序项的相对位置与排序之前保持不变，则称此排序方法是稳定性排序，否则为非稳定性排序。
例如，参加排序的依次是：a1 = 3, a2 = 6, a3 = 18, a4 = 3, a5 = 18;
若是稳定性排序，则排序结果一定是:
a1 = 3, a4 = 3, a2 = 6, a3 = 18, a5 = 18;
若是非稳定性排序，则排序结果可能会是：
a4 = 3, a1 = 3, a2 = 6, a3 = 18, a5 = 18;
这样a1 和a4 的相对位置改变。
1. 直接插入排序
设存在一个一维数组 array[0..n-1], 第 i 趟排序是将数组中下标为 i 的第 i + 1 个元素插入到一个已经按值有序排列的子序列的合适位置。
1. 插入排序开始时， 第一个元素看成有序序列，从下标为 i = 1 的第二个元素开始，每一趟排序都将下标为 i 的元素插入到之前的有序序列中，然后 i = i + 1 进行下一个元素的插入排序，由此可见插入排序需要 n - 1 趟排序
2. 每次寻找插入元素 array[i] 的位置时是从有序序列的最后一个元素 array[i-1] 开始查找，直到找到某一位置的元素 array[j] (j >= 0 && j <= i-1)满足 array[j] <= array[i], 那么下标为
j + 1 的位置就应该是插入元素 array[i]的合适位置。从有序序列的最后一个元素开始查找，边查找边移动元素，而不是先找到插入位置再移动元素，这样提高了效率。
3. 将array数组中下标 [j + 1， i - 1]的所有元素依次后移一位，空出 array[j+1]的位置。
4. 将array[i] 元素赋值给 array[j+1]， 至此完成插入排序的一趟排序。
看代码：
#include <stdlib.h>
#include <stdio.h>
void simple_insertSort(int array[], int n)
{
int i, j;
int temp;
for(i = 1; i < n; ++i)
{
temp = array[i];
j = i - 1;
while(j >= 0 && temp < array[j])
{
array[j+1] = array[j];
--j;
}
array[j+1] = temp;
}
}
int main()
{
int array[] = {5, 15, 3, 20, 11};
simple_insertSort(array, sizeof(array)/sizeof(int));
for(int i = 0; i < 5; ++i)
printf("%d ", array[i]);
printf("\n");
}
注意：
1. 为保证插入排序是稳定性排序，在while循环时判断条件是temp < array[j], 而不是temp <= array[j];
2. 最后插入元素temp的合适位置应该是 j + 1， 下标为 j 的位置应该是 temp >= array[j] 的第一元素，我们应该在该元素之后插入元素。
时间复杂度分析：
1. Best case，当原始序列是一个按值递增序列时，对应的每个i值只需要进行一次元素之间的比较，因而总的比较次数最少，为 n - 1，并且不需要移动元素。
2. Worst case，当原始序列是一个按值递减的序列时，对应的每个i值都需要进行 i - 1 次比较，总的元素之间的比较次数达到最大值，为
1 + 2 + 3 + 4 + . . . + n - 1 = n(n-)/2
3. Average case, 序列的初始情况是随机的，即参加排序的序列中元素可能出现的各种排列的概率相同，则可取上述最小值和最大值的平均值作为插入排序时所进行的元素之间的比较次数，约为 n^2/4
由此可见出入排序的时间复杂度为 O(n^2)
插入排序属于稳定性排序方法。
2. 折半插入排序
从上述的分析中可以看出，每一趟被插入的子序列是一个按值有序的序列，因而可以采用折半查找的方法来确定插入元素的该有序序列中的合适位置。
折半查找需要设定三个中间变量 low ， mid，high，在一趟插入排序的初始情况下，low = 0， high = i - 1. 于是 mid = (low + high) / 2;
如果需要插入的元素array[i] < array[mid], 则 array[i] 的插入位置应该在 mid 的左侧，令 high = mid - 1；
如果需要插入的元素array[i] >= array[mid], 则array[i]的插入位置应该在 mid 的右侧，令 low = mid + 1;
再令 mid = (low+high) / 2, 重复上述比较步骤
在折半查找结束时，一定有 mid = low = high, 这时再进行最后一次比较，
如果 array[i] < array[mid], 则应该在 array[mid]的前面插入元素array[i]，也就是需要将序列中[low，i - 1]的元素依次后移一位后，再进行array[low] = array[i]的赋值操作。这时
high = mid - 1，会导致 low > high
如果 array[i] >= array[mid]，则应该在array[mid]的后面插入元素array[i]，这时 low = mid + 1，也是将[low，i - 1]的元素一次后移一位后，再进行array[low] = array[i]的赋值操作，
这时 low > high.
由此可见，折半查找循环结束的条件应该是 low > high.
看代码：
#include <stdlib.h>
#include <stdio.h>
void bin_insertSort(int array[], int n)
{
int i, j, temp, low, high, mid;
for(i = 1; i < n; ++i)
{
temp = array[i]; //将当前需要被插入元素保存在temp中
low = 0;
high = i - 1;
while(low <= high) //利用折半查找确定被插入元素array[i]的合适位置
{
mid = (low + high) / 2;
if(temp < array[mid])
high = mid - 1;
else
low = mid + 1;
}
for(j = i - 1; j >= low; --j) //找到合适位置low, 将[low, i-1]中的元素依次后移一位
array[j + 1] = array[j];
array[low] = temp; //插入元素array[i], 至此插入排序的一趟结束
}
}
int main()
{
int array[] = {3, 1, 12, 15, 9};
int n = sizeof(array) / sizeof(int);
bin_insertSort(array, n);
for(int i = 0; i < n; ++i)
{
printf("%d ", array[i]);
}
printf("\n");
}