一、插入排序

1.算法思想

要求在一个已经有序的数据序列中插入一个数据，并且插入次数据后数据序列依然有序，这时就需要用到一种新的排序方法——插入排序，其基本思想就是每步讲一个待排序的记录，按其关键码值的大小插入到前面已经排序的文件中适当的位置，直至全部插入完为止。

2.具体步骤

1. 从第一个元素开始，该元素可以认为已经被排序
2. 取出下一个元素，在已经排序的元素序列中从后向前扫描
3. 如果已排序的元素大于新元素，将其移到下一位置
4. 重复步骤3，直至找到已排序的元素小于或者等于新元素的位置
5. 将新元素插入
6. 重复步骤2-5

3.算法复杂度

时间复杂度：如果将n个元素升序排列，最好的情况是已经升序，这种情况下，只需要进行(n-1)此比较即可；最坏的情况是降序排列，此时需要比较n(n-1)/2次。平均时间复杂度为o(n^2)。

空间复杂度：o(1)

稳定性：在插入过程中，如果碰见一个和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后顺序没有改变，是稳定的。

void InsertSort(int* arr,size_t size)
{
	if (NULL == arr || size == 1)
		return;
	for (size_t i = 1; i < size; i++)
	{
		int key = arr[i];
		int end = i - 1;
		while (key < arr[end] && end >= 0)
		{
			arr[end + 1] = arr[end];
			end--;
		}
		arr[end + 1] = key;
	}
}

在插入数据过程中，比较次数可能会比较多，我们可以将直接查找的方改为折半查找，即可得到折半插入排序算法，相比于直接插入排序，有一定的优化。

void InsertSort_B(int* arr,size_t size)
{
	if (NULL == arr || size == 1)
		return;
	for (size_t i = 1; i < size; i++)
	{
		int key = arr[i];
		int left = 0;
		int right = i - 1;
		int end = i - 1;
		while (left <= right)
		{
			int mid = left + ((right - left) >> 1);
			if (key < arr[mid])
				right = mid - 1;
			else
				left = mid + 1;
		}
		while (left <= end)
		{
			arr[end + 1] = arr[end];
			end--;
		}
		arr[end + 1] = key;
	}
}

二、希尔排序

1.算法思想

希尔排序又称缩小增量法，是直接插入排序的一种改进。其基本思想是：先取一个小于n的整数d1作为第一个增量，把文件的全部记录分组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2<d1重复上述的分组和排序，直至所取的增量 dt=1，即所有记录放在同一组中进行直接插入排序为止。

该方法实质上是一种分组插入的方法。

2.具体步骤

假设有10个记录，其关键字分别是：7,5,3,1,9,4,6,2,8；取增量依次为3,1

3.算法分析

希尔排序不需要大量的辅助空间，容易实现。相比于插入排序，效率上有所提高，其时间复杂度也有增量的选取有关。希尔排序没有快速排序快，对于规模非常大的数据排序不是最优的选择；但是希尔排序在最坏的情况下和平均情况下执行效率相差不是很大，快速排序则相差较大，因此，几乎任何排序工作在开始时都可以用希尔排序，若在实际中证明它不够快，再改成快速排序。此外，希尔排序是不稳定的。

void ShellSort(int* arr,size_t size)
{
	int gap = size;
	while (gap > 1)
	{
		gap = gap / 4 + 1;
		for (size_t i = gap; i < size; i++)
		{
			int key = arr[i];
			int end = i - gap;
			while (key < arr[end] && end >= 0)
			{
				arr[end + gap] = arr[end];
				end -= gap;
			}
			arr[end + gap] = key;
		}
	}
}