【数据结构初阶之插入排序】：插入排序和希尔排序

• 插入排序
• 直接插入排序
• 希尔排序

插入排序，是一种简单的插入排序方法，它的基本思想是：把待排序的记录按其关键值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列。
插入排序最简单的就是直接插入排序，而对插入排序的优化就有了希尔排序，下面我们分别来分析。

直接插入排序在其实现过程使用双层循环，外层循环控制有序序列的最后一个下标，内层循环对当前元素前面有序表进行待插入位置查找，并进行移动。
我们先分析把一个元素插入到有序数组的过程，图片如下：
我们搞定了把一个元素插入到有序区间中了，但是这么搞定把所有元素全部排成有序呢？
我们知道当区间只有一个元素的时候，这个区间就有序了。
所以我们控制下标end从0开始就可以了，因为当下标end为0说明区间只有一个元素是有序的，后面我们不断插入就可以了
代码如下：

//直接插入排序
void InsertSort(int* p, int n)
{
	int i = 0;
	//外层循环控制产生有序区间的最后一个元素的下标
	for (i = 0; i < n - 1; i++)
	{
		int end = i; //end为有序区间的最后一个元素的下标
		int x = p[end + 1]; //x为要插入的元素


		//内层循环控制找比x要小的元素，有两种可能
		//1.在数组中可以找到，从break退出
		//2.在数组中找不到比自己小的，从while(end>=0)退出
		while (end >= 0)
		{
			if (p[end] > x)
			{
				p[end + 1] = p[end];
				end--;
			}
			else
			{
				break;
			}
		}
		//最后把保存的x值插入即可
		p[end + 1] = x;
	}
}

我们上面学了普通的插入排序，如果我要插入的元素很小，但是被插入数组的因素却非常多，很可能要从末端比较到前端才找到合适的插入位置。所以针对这个缺点，我们有了希尔排序，就是在插入排序的基础上进行的优化。
希尔排序先预排序数组，把数组分成gap组，然后间隔为gap的就为一组，先对组内进行插入排序，这样小的数就非常快的跳到前面，大的数非常快的跳的后面，就不用一个一个进行比较；而预排序完后就进行插入排序，这样就能把时间复杂度优化到O(N^1.3).
希尔排序的重点过程如下：

代码实现如下：

#include 
#include 

//打印函数
void Print(int* p, int n)
{
	int i = 0;
	for (i = 0; i < n; i++)
	{
		printf("%d ", p[i]);
	}
	printf("n");
}

//希尔排序
void ShellSort(int* p, int n)
{
	int gap = n;
	int i = 0;
	while (gap > 1)
	{
		//gap不断地缩小到1
		//并且gap控制分组
		gap = gap / 2;
		//对所有组都进行排序
		for (i = 0; i < n - gap; i += gap)
		{
			int end = i;
			int x = p[end + gap];
			while (end >= 0)
			{
				if (p[end] > x)
				{
					p[end + gap] = p[end];
					end = end - gap;
				}
				else
				{
					break;
				}
			}
			p[end + gap] = x;
		}
	}
}

int main()
{
    //三组测试用例
	int arr1[] = { 4,1,3,2,9,8,6,5,7 };
	int sz1 = sizeof(arr1) / sizeof(arr1[0]);

	int arr2[] = { 5,8,44,22,0,5,8,1,3 };
	int sz2 = sizeof(arr2) / sizeof(arr2[0]);

	int arr3[] = { 2,5,99,3,8,11,33,62 };
	int sz3 = sizeof(arr3) / sizeof(arr3[0]);

	printf("希尔排序结果如下：n");
	Print(arr1, sz1);
	ShellSort(arr1, sz1);
	Print(arr1, sz1);
	printf("n");

	Print(arr2, sz2);
	ShellSort(arr2, sz2);
	Print(arr2, sz2);
	printf("n");

	Print(arr3, sz3);
	ShellSort(arr3, sz3);
	Print(arr3, sz3);
	printf("n");

	return 0;
}

代码执行如下：