希尔排序

缘起

本文介绍一下一种直接插入排序的推广——希尔（Shell）排序. 该算法基于以下事实：如果一个序列基本有序，那么用直接插入排序是非常快的，因为while的第一步就会终止. 希尔排序就是选取一定的步长，将序列整的基本有序（所谓基本有序是指大的数基本在后面，小的数基本在前面，而不是局部有序）
ps：因为涉及不相邻元素之间的调换，所以希尔排序不是稳定排序，但是显然是就地算法.

分析

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include "stdafx.h"
#include <cstdio>
using namespace std;

//#define LOCAL

// 对含有n个元素的数组进行shell排序
void shellSort(int *a, int n)
{
	int gap = n; // 步长是n, 所谓步长的解释是, 例如本例子中gap如果是5的话, 则本数组就分成了 99 、17、 25 ; 5、 46、 28; 36、 12、 1; 7、 2、 92; 22、19 这几组. shell排序就是对于固定的gap，将每组数整的有序, 即做到局部有序, 而且间隙越小,局部有序的粒度越细,即就越接近整体有序
	do 
	{
		gap = gap/3+1;
		for (int i = gap; i<n; i++) // 从 a[gap,...,n-1] 开始
		{
			int j = i,tmp = a[i];
			while(j>=gap && a[j-gap] > tmp)
			{
				a[j] = a[j-gap]; // 后移动一格
				j-=gap;
			}
			a[j] = tmp;
		}
	} while (gap>1);
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
#endif

	int a[14]={99,5,36,7,22,17,46,12,2,19,25,28,1,92};
	shellSort(a,14);
	for (int i = 0; i<14; i++)
	{
		printf("%d ",a[i]);
	}
	return 0;
}

希尔排序的循环体中每次都是 O(n)的复杂度, 所以shell排序的复杂度是O(nlogn)