直接插入排序法、折半插入排序法以及希尔排序法

直接插入排序法：

//arr表示待排序的数组，length表示数组的长度
void InsertSort(int arr[], int length)
{
	int i, j;
	//arr[0]直接插入排序的序列中，故从i=1开始排
	//外部更替
	for (i = 1; i < length; i++)
	{
		//先通过比较判断arr[i]是否是一个较小值
		if (arr[i] < arr[i - 1])
		{
			//先保存arr[i]的值
			int temp = arr[i];
			//内部比较并移动
			for (j = i - 1; j >= 0; j--)
			{
				if (temp < arr[j])
				{
					arr[j + 1] = arr[j]; //每次比较后,arr[j]都往后退一步
				}
				else
				{
					//如果temp已经找到自己的合适位置，那么退出循环
					break;
				}
			}
			//因为j指向的是比temp还小的元素，故temp应该排在j+1这个位置
			arr[j + 1] = temp;
		}
	}
}

折半插入排序法是由直接插入法改进而来的：主要改进的地方就是查找部分，通过折半查找法快速找到合适的插入位置。

折半插入排序法：

void BInsertSort(int arr[],int length)
{
	int i;
	for (i = 1; i < length; i++)
	{
		int temp = arr[i];
		int high = i - 1;
		int low = 0;
		//通过折半查找法找到适合temp的位置
		while (low<=high)//当查找区间只剩下一个元素时，必定有 low=high
		{
			//当low=high时，经过以下程序，必有low比high大1
			int mid = (high + mid) / 2;
			if (temp < arr[mid])
			{
				high = mid - 1;
			}
			else
			{
				low = mid + 1;
			}
		}
		//经过折半查找以后，high必定比low小1，即  low=high+1;
		//而插入元素的位置必然是low或high+1(因为low==high+1)
		//然后移动元素，为temp空出位置
		int j;
		for (j = i - 1; j >= low; j--)
		{
			arr[j + 1] = arr[j];
		}
		arr[low] = temp;

	}
}

希尔排序法也是经过直接插入法改进而来的，其本质就是多重插入排序，效率提升的原因是本来较小的元素需要挨个移动，而希尔排序直接跨越移动，减少了元素的移动次数。故希尔排序相较于直接插入排序，其改进的地方就是移动元素的部分。当希尔增量等于1的时候，就是直接插入排序法，但是经过之前多轮不同增量下的插入排序，最后一轮排序时，整个数组已经变得相对有序很多了。

希尔排序法：

void ShellSort(int arr[], int length)
{
	int inc; //希尔增量
	//这里采用朴素希尔增量，即每次增量都是上一次的一半
	for (inc = length / 2; inc >= 1; inc = inc / 2)
	{
		//这里i=inc,就好比直接插入排序中的i=1一样，都是第一个元素首先直接插入
        //这里的循环条件依旧是i<length,希尔增量只是使每轮比较的元素个数减少，
        //而不会使外部的更替次数减少
		for (int i = inc; i < length; i++)
		{
			//加上个if语句使效率更高，当arr[i]>arr[i-inc]时直接开始下轮循环
			//但是去掉if判断也不影响结果
			if (arr[i] < arr[i - inc])
			{
				//temp首先记录arr[i]的值
				int temp = arr[i];
				int j;
				//比较并移动元素
				for (j = i - inc; j >= 0 && temp < arr[j]; j = j - inc)
				{
					arr[j + inc] = arr[j];
				}
				//j指向的元素必定小于等于temp,故yemp插入的位置为j+inc
				arr[j + inc] = temp;
			}
		}
	}
}