算法笔记--希尔排序

希尔排序是直接插入排序的改进版，对于待排序序列的不同情况效率相近。

1. 算法思想

          先选取一个小于n的增量d1，把序列中所有元素分成d1个组，所有距离为d1的倍数的元素在同一组中，在各组内执行直接插入排序。然后选取一个更小的增量d2，重复上述分组和排序过程；继续减小增量，直至增量为1，即所有元素在同一组中直插排序。

          因此希尔排序又叫缩小增量排序法。

2. 时间复杂度

          最好情况 O(n^1.3)：与增量序列的选取有关，尚未定论最好情况的复杂度是多少，目前找出最好的好像是n的1.3次方
          最坏情况 O(n^2)：Mark Allen Weiss 的《Data Structures and Algorithm Analysis in C》一书中有论证

3. 空间复杂度 O(1)

          就地排序，辅助空间为常数级

4. 稳定性

          不稳定。存在不相邻元素之间的交换

5. 代码实现（C语言）

          代码中使用的增量序列是不断除2的方法，这是希尔排序最初使用的序列，效率比较低。

void ShellSort(int *A, int n)
{
	int i, j;
	int tmp;
	int d = n / 2;

	while (d)
	{
		for (i = d; i < n; ++i)
		{
			j = i;
			tmp = A[j];

			while(j >= d && tmp < A[j - d])
			{
				A[j] = A[j - d];
				j -= d;
			}

			A[j] = tmp;
		}

		d = d / 2;
	}
}