希尔排序

希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。

希尔排序是基于插入排序的以下两点性质而提出改进方法的：

• 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率；
• 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位；

希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录"基本有序"时，再对全体记录进行依次直接插入排序。

算法步骤

选择一个增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1；

按增量序列个数 k，对序列进行 k 趟排序；

每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

代码实现

void ShellSort(int *a, int n)
{
	int gap = n ;
		while (gap > 1)
	{ 
			//gap /= 2;
			gap = gap/3+1;
		for (int i = 0; i < n - gap; i += 1)  //n个数排列，只需排n-1个，（因为第一个必定有序--默认）
		{
			/*第一个数排序*/
			int end = i;  //下标 ， 已排序数组【0 - end】
			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; //插在end后面
		}
	}
}