插入排序

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

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

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

直接插入排序

理论

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

算法实现

void InserSort(ElemType A[], int n)
{
	int i, j;
	for(i=2;i<=n;i++)
		if (A[i] < A[i - 1])
		{
			A[0] = A[i];
			for (j = i - 1; A[0] < A[i]; --j)
				A[j + 1] = A[j];
			A[j + 1] = A[0];
		}
}

折半插入排序

折半插入排序将比较和移动操作分离，即先折半查找出元素的待插入位置，然后统一地移动待插入位置之后的所有元素。

算法实现

void half_Insert(ElemType A[], int n)
{
	int i, j, low, high, mid;
	for (i = 2; i <= n; i++)
	{
		A[0] = A[i];
		low = 1;
		high = i - 1;
		while (low <= high)
		{
			mid = (low + high) / 2;
			if (A[mid] > A[0])
				high = mid - 1;
			else
				low = mid + 1;
		}
		for (j = i - 1; j >= high + 1; --j)
			A[j + 1] = A[j];

		A[high + 1] = A[0];
		
	}
}

希尔排序

概念

希尔排序的基本思想是：先将排序表分割成若干形如L[i，i+d,i+2d…i+kd]的“特殊”子表，即把相隔某个“增量”的记录组车一个子表，对各个子表分别进行直接插入排序，当整个表中的元素已经基本有序时，再对整个表进行一次直接插入排序。
一般情况下，第一个增量一般选用n=总元素数/2；

算法实现

void shell_Sort(ElemType A[],int n)
{
	int i, j, dk;
	for (int dk = n / 2; dk >= 1; dk--)
		for(int i=dk+1;i<=n;i++)
			if (A[i] < A[i - dk])
			{
				A[0] = A[i];
			}
	for (int j = i - dk; j > 0 && A[0] < A[j]; j -= dk)
		A[j + dk] = A[j];
	A[j + dk] = A[0];


}