数据结构：插入排序和希尔排序

插入排序

逆序的情况下：       时间复杂度：O(N^2)                                             空间复杂度：O(1)

顺序的情况下：       时间复杂度：O(N)                                                 空间复杂度：O(1)

   1、插入排序的思想

        插入排序在我们生活中最常见的例子就是打牌时候的理牌的过程，可以看作为插入排序。我们拿一个数，先和数组的第一个数比较，比它小就插入，比它大就放到它的后面。

   2、代码实现

        我们先实现单趟的排序。按照上面的思想，先取数组的一位数据tmp与前面的数end比较，比它小就插入，比它大就放到它的后面。但不是直接的插入，因为我们还不确定更前面有没有比tmp小的数据，所以若遇到比tmp要大的数就直接后移，直到遇到比tmp小的数，就把tmp赋值到end+1的位置。

void InsertSort_Test(int* arr, int n)
{
    //arr为数组首元素的地址，n为数组的大小
	int end = i;//i为end要开始的位置
	int tmp = arr[end + 1];
    while (end >= 0)
	{
	    if (arr[end] > tmp)
	    {
		    arr[end + 1] = arr[end];
		    end--;
	    }
		    else
	    {
	    	break;
	    }
	}
	arr[end + 1] = tmp;
}

        然后我们要实现多趟的排序， 只需要改变 i 的值就可以改变end和tmp，使其可以多次的单趟排序直至排好。注意：这里的i < n - 1,因为下面的 tmp = arr[end + 1]。

void InsertSort_Test(int* arr, int n)
{
	for (int i = 0; i < n - 1; i++)
	{
		int end = i;
		int tmp = arr[end + 1];

		while (end >= 0)
		{
			if (arr[end] > tmp)
			{
				arr[end + 1] = arr[end];
				end--;
			}
			else
			{
				break;
			}
		}
		arr[end + 1] = tmp;
	}
}

 希尔排序

平均时间复杂度：O(N^1.3)                                             空间复杂度：O(1)

   1、希尔排序的思想

        希尔排序的思想与插入排序很像，不过希尔排序将数组分为了很多小组进行插入排序，然后缩小组的大小直至1，那就跟插入排序一样了。

   2、代码实现

        为了实现组gap可以分到1，我们可以这样gap = gap / 3 + 1,保证gap可以到1。

void ShellSort_Test(int* arr, int n)
{
	int gap = n;
	while (gap > 1)
	{
		gap = gap / 3 + 1;

		for (int i = 0; i < n - gap; i++)
		{
			int end = i;
			int tmp = arr[end + gap];

			while (end >= 0)
			{
				if (arr[end] > tmp)
				{
					arr[end + gap] = arr[end];
					end -= gap ;
				}
				else
				{
					break;
				}
				arr[end + gap] = tmp;
			}
		}
	}
}