【数据结构排序算法（二）】希尔排序

基础数据结构之八大排序算法（二）

②希尔排序（对直接插入排序的优化），最小增量排序

时间复杂度：O（1.3）~ O（1.5） 通过最小增量数组对数据进行排序，每个最小增量进行一次排序（每次排序使数据更为有序，则下次时间复杂度变小）

空间复杂度：O（1） 所有额外辅助变量不会影响整体问题的规模

稳定性：不稳定 存在跳跃交换

（以顺序表作为待排序对象）

1.基本思想：

以数组 { 7 6 5 9 3 18 21 8 22 10 66 77 35 91 29 } 为例。
最小增量数组为{ 5 3 1 }

**注意：最小增量数组中的最后一个最小增量必须是1 ！！！
最后必须通过增量为1，将所有数据再排序一次，不然永远不会有序

<1>.最小增量为5时：
从第一个数据向后数到的第5个数据为一组，直到向后不够5个数据停止，再从第二个数据开始向后数到的第5个数据为一组，重复此操作直到最后一个数据也被分组停止。（解释如下图所示）

<2>.最小增量为3时：
在最小增量为5排序后的基础上，从第一个数据向后数到的第3个数据为一组，直到向后不够3个数据停止，再从第二个数据开始向后数到的第3个数据为一组，重复此操作直到最后一个数据也被分组停止。（解释如下图所示）


<3>.最小增量为1时：
在最小增量为3排序后的基础上，将所有数据遍历一遍，全部排序一遍后数组有序。

2.代码实现

（1）包含的头文件和宏替换：

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>

#define ELEM_TYPE int
#define ar arr[]={18,21,8,9,10,7,6,5,91,3,66,77,35,22,29}

int ar;
1
2
3
4
5
6
7
8

（2）顺序表的建立：

typedef struct Sqlist
{
	ELEM_TYPE* data;
    int length;
    int SIZE;
}Sqlist,*PSqlist;
1
2
3
4
5
6

（3）顺序表的初始化：

void Init_Sqlist(PSqlist L)
{
	L->data=arr;
	L->length=0;
	L->SIZE=sizeof(arr)/sizeof(arr[0]);
}
1
2
3
4
5
6

（4）打印数据：

void Show(PSqlist L)
{
	for(int i=L->length;i<L->SIZE;i++)
	{
		printf("%d ",L->data[i]);
	}
	printf("\n\n");
}
1
2
3
4
5
6
7
8

（5）希尔排序

希尔排序就是直接插入排序的优化版，只是比直接插入排序多了用最小增量分组，其对每一组的排序依然可以看成直接插入排序

void Shell(PSqlist L,ELEM_TYPE gap)
{
	for(int i=L->length+gap;i<L->SIZE;i++)
	{
		ELEM_TYPE tmp=L->data[i];
		int j=i-gap;
		for(j;j>=0;j-=gap)
		{
			if(tmp<L->data[j])
			{
				L->data[j+gap]=L->data[j];
			}
			else
			{
				break;
			}
		}
		L->data[j+gap]=tmp;
	}
}

void ShellSort(PSqlist L)
{
	int gap[]={5,3,1};
	int gap_len=sizeof(gap)/sizeof(gap[0]);
	for(int i=0;i<gap_len;i++)
	{
		Shell(L,gap[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
26
27
28
29
30

（6）主函数

int main()
{
	Sqlist head;
	Init_Sqlist(&head);
	printf("初始数据：");
	Show(&head);
	printf("希尔排序后数据：");
	ShellSort(&head);
	Show(&head);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11

（7）运行结果

希望这篇博客能帮助大家更好的学习和理解希尔排序
感谢阅读！