数据结构-希尔排序

1.原理

6	5	2	7	12	15	1	4	3	9	8	10
5排序
6	15	8
5	1	10
2	4
7	3
12	9
结果：
6	1	2	3	9	8	5	4	7	12	15	10
3排序
6	3	5	12
1	9	4	15
2	8	7	10
结果：
3	1	2	5	4	7	6	9	8	12	15	10
1排序：
1	2	3	4	5	6	7	8	9	10	12	15

因每趟的排序间隔逐渐减小，希尔排序也称为缩小增量排序

2.代码

#include 
#include 

/* run this program using the console pauser or add your own getch, system("pause") or input loop */
//辅助函数：打印数组 
void print_arr(int arr[],int n)
{
	int i;
	for(i=0;i<n;i++)
		{
			printf("%d ",arr[i]);
		}
	putchar('\n');
} 
//希尔排序
void shell_sort(int arr[],int n)
{
	int i,j,inc,key;
	//初始增量n/2,每一趟之后除以2 
	for(inc=n/2;inc>0;inc/=2)
	{
//		每一趟使用插入排序
 		for(i=inc;i<n;i++)
 		{
 			key = arr[i];
 			for(j=i;j>=inc&&key<arr[j-inc];j-=inc)
 			{
 				arr[j] = arr[j-inc];
 			}
 			arr[j]=key;
 		}
 		print_arr(arr,n);
	} 
} 
int main(int argc, char const *argv[]) {
	int arr[] = {15,5,2,7,12,6,1,4,3,9,8,10};
	print_arr(arr,12);
	shell_sort(arr,12);
	return 0;
}

3.时间复杂度

希尔排序时间复杂度依赖于增量序列
除了一些简单的序列，其它序列的复杂度证明是一个长期未解决的问题
所有序列中最坏情况：O（N的平方）
Hibbard增量序列：
最坏的情况：O（N的二分之三次方）
模拟平均情况[无人证明]：O（N的四分之五次方）
Sedgewick增量序列
最坏：O（N的三分之四次方）
模拟平均结果[猜测]：O（N的六分之七次方）