希尔排序

发表于 | 阅读次数:

希尔排序

参考：
https://baike.baidu.com/item/%E5%B8%8C%E5%B0%94%E6%8E%92%E5%BA%8F

http://cuijiahua.com/blog/2017/12/algorithm_3.html

一、原理

希尔排序是插入排序的一种，又称“缩小增量排序”，是直接插入排序的一种高效改进版。

二、步骤

  • 1、先取一个增量$a_{1}$,然后将待排序的序列按照将距离为$a_{1}$的数放在一组中的原则分成n组，（最后不够$a_{1}$个的数也为一组）
  • 2、将所有组数分别进行直接插入排序
  • 3、排好序后再将所有组的数拼接在一起
  • 4、重新选择一个增量$a_{2}$，使得$a_{2}<a_{1}$，然后重复上诉步骤即可，直到增量为1，排序完成

三、例子

假设有一组数{0,10,1,2,8,5,9,7,3,4,6}，增量步长为3进行排序：

1
2
3
0    2    9    4
10   8    7    6
1    5    3

对每组进行直接插入语排序

1
2
3
0    2    4    9
6    7    8    10
1    3    5

将上述每组元素依此拼接在一起得到{0,2,4,9,6,7,8,10,1,3,5},然后在以2为增量步长进行排序：

1
2
0    4    6    8    1    5
2    9    7    10   3

对每组进行直接插入排序

1
2
0    1    4    5    6    8
2    3    7    9    10

最后再以1为增量步长进行排序（就是简单的直接插入排序了）。

四、算法实现

C语言

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
41
42
43
44
45
46
47
48
49
50
#include "stdio.h"

void shell_sort(int a[], int n);

void shell_sort(int a[], int n)
{
	int gap,i,j,temp,loop_num=0;
	for (gap = n >> 1; gap > 0; gap >>=1)
	{
		loop_num++;
		for (i = gap; i < n; i++)
		{
			temp = a[i];
			j = i - gap;
			while (j >= 0 && a[j]>temp)
			{
				a[j + gap] = a[j];
				j -= gap;
			}
			a[j + gap] = temp;
		}
		printf("第%d次循环,gap=%d：\t", loop_num,gap);
		for (j = 0; j < n; j++)
		{
			printf("%d\t", a[j]);
		}
		printf("\n");
	}
}

int main()
{
		int number[] = { 0,10,1,2,8,5,9,7,3,4,6 };
		int i;
		int n = sizeof(number) / sizeof(number[0]);
		printf("原始数据：\n");
		for (i = 0; i < n; i++)
		{
			printf("%d\t", number[i]);
		}
		printf("\n\n");
	
		shell_sort(number, n);
		printf("\n返回结果：\n");
		for (i = 0; i < n; i++)
		{
			printf("%d\t", number[i]);
		}
		printf("\n");
}

运行结果