插入排序和希尔排序

1.直接插入排序

基本思想：
把待排序的数据按其大小逐个插入到一个已经排好序的有序序列中，直到所有的数据插入完成为止。

当插入第i个元素时，前面的a[0],a[1],...,a[i-1]个数据已经排好序了，此时用a[i]与a[i-1],a[i-2],...进行比较，找到插入位置就将a[i]插入，原来位置上的元素顺序后移

void InsertSort(int* a, int n)
{
	for (int i = 0; i < n-1; i++)
	{
		int end = i;//记录已经有序的数据的最后一个数据的下标
		int tmp = a[end + 1];
		while (end >= 0)
		{
			if (a[end] > tmp)
			{
				a[end + 1] = a[end];
				end--;
			}
			else//a[end]
			{
				break;
			}
		}
		a[end + 1] = tmp;
	}
}

元素集合月接近有序，直接插入排序算法的时间效率更高
时间复杂度：O(N^2)
稳定性：稳定

2.希尔排序

希尔排序是直接插入排序的优化

1.预排序
2.直接插入排序
基本思想：
先选定一个整数，把待排序文件中所有数据分成gap个组，所有距离为gap的数据分在同一个组里，并对每一组的数据进行排序。然后，取gap=gap/3+1，重复上述分组的操作。当gap=1时，所有数据在同一组的已经排好序了

void ShellSort(int* a, int n)
{
		int gap = n;
		while(gap > 1)
		{
			//+1保证最后一个gap一定是1
			//gap》1是预排序
			//gap==1是插入排序
			gap = gap / 3 + 1;
			for (int i = 0; i < n - gap; i++)
			{
				int end = i;
				int tmp = a[end + gap];
				while (end >= 0)
				{
					if (a[end] > tmp)
					{
						a[end + gap] = a[end];
						end -= gap;
					}
					else
					{
						break;
					}
				}
				a[end + gap] = tmp;
			}
		}
}

当gap>1时都是预排序，目的是让数组更接近有序。当gap==1时，数组已经接近有序了，这样就会很快
时间复杂度：O（N^1.3)（ps：时间复杂度是不固定的）
稳定性：不稳定