排序算法之插入排序（直接插入排序、折半插入排序、希尔排序）

插入排序

在排序过程中，根据数据元素是否完全在内存中，可以将排序分成两类：

1. 内部排序：是指在排序期间元素全部存放在内存中的排序。内部排序在执行过程中都要进行两种操作：比较和移动。
2. 外部排序：是指在排序期间元素无法全部同时存放在内存中，必须在排序的过程中根据要求不断地在内、外存之间移动的排序。外部排序还要关注如何使读/写磁盘次数更少。

插入排序的思想是每次将一个待排序的记录按其关键字大小插入前面已排好序的子序列，直到全部记录插入完成。 插入排序思想可以引申为三种重要的排序算法：直接插入排序、折半插入排序、希尔排序

直接插入排序 理论

直接插入是一个稳定的排序方法，适用于顺序存储和链式存储的线性表。 算法的思想是：依次将每个元素插入到前面已经排序好的子表的相应位置中。

算法实现

void InserSort(ElemType A[], int n)
{
	int i, j;
	for(i=2;i