排序算法——希尔排序

什么是希尔排序

希尔排序也叫做：缩小增量排序。 分组（分组的组数需要循环递减，直到减为1）排序。
先将待排序序列分成若干组，然后使用直接插入排序在组内排序。循环着将分组数减小，执行以上过程。直到分组减为1. 所有的分组数都互质。

分组可为任意数字，且每次分组数都比上一次分组要小，直至分组数为1。

为什么不直接使用插入排序

相比较插入排序，希尔排序输入直接插入排序的一种，但是在两种算法的比较上

希尔排序: 就是直接插入排序的优化， 数据越有序，排序越快
时间复杂度： 时间复杂度是与增量序列相关的函数 O(n^1.3~1.5)
空间复杂度： O(1)
稳定性： 不稳定
直接插入排序
时间复杂度： 等差数列 O(n^2)
数据序列已经有序，则能达到最好时间复杂度: O(n)
数据趋于有序（部分有序）: 时间复杂度就可以趋于 O(n)，–> 数据越有序，时间复杂度越低。
空间复杂度： O(1)
稳定性： 稳定的

对于一个长度为10000的需要排序的数组，希尔排序只需要更少的比较次数与交换次数。

希尔排序代码实现

void Shell(int *arr, int len, int width)
{
	for(int i = width; i < len; ++i)
	{
		int tmp = arr[i];
		int j = i - width;

		for(; j >= 0 && arr[j] > tmp; j -= width)
		{
			arr[j+width] = arr[j];
		}

		arr[j+width] = tmp;
	}
}

void ShellSort(int *arr, int len)
{
	int group[] = {5, 3, 1};

	for(int i = 0; i < sizeof(group)/sizeof(group[0]); ++i)
	{
		Shell(arr, len, group[i]);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

很显然，希尔排序不过对直接插入排序前进行了一次分组。分组使得希尔排序对于大量的数据处理更有优势，但是也增加了不稳定性。