排序之希尔排序：草根逆袭记_业界新闻

发布时间:2024-08-07 22:26

阅读量:0

🍺0.前言

言C之言，聊C之识，以C会友，共向远方。各位博友的各位你们好啊，这里是持续分享C语言知识的小赵同学，今天要分享的C语言知识是希尔排序，在这一章，小赵将会向大家展开希尔排序。✊

👀1.希尔排序

希尔排序为什么被小赵叫作草根逆袭的算法呢？因为它是在插入排序的基础上发展出来的，而为什么插入排序是草根呢？因为我们只要用上节课学的时间复杂度的知识去算插入排序的时间复杂度就会发现它的时间复杂度几乎就是 O (N*N),而这样的时间复杂度，在大多数情况下我们的程序都是不会去使用的，而希尔这个天才人物就在这个算法的基础上开发了一种能够和当前很多很牛的快速排序算法相媲美的算法，你说它是不是草根逆袭呢？好了废话不多说，直接上菜。

✍1.1希尔排序的原理

希尔排序就究竟是怎么做到的呢？其实就是将我们数组进行了分组，然后挨个进行插入排序。而这个分组也有讲究是每隔几个位置进行一次分组。在这里小赵从网上找来了个动图觉得很形象，分享给大家。

不同颜色作为一个分组，进行插入排序，那这样的好处是什么呢？小赵的理解是这样的一次分组会让大数在后面，小数在前面，那么我们原本插入排序在插入时候，要向后移动的次数就会减少。这样就让本身的时间很长的插入排序变得很快。

🚝2.希尔排序初步

🚈2.1每一组排序

跟上次一样，我们先想如何完成我们分的每一组的一次排序呢？可以参考小赵下面的代码

int n;//n为要排序的数组的元素的数量 int gap;//以多少为间距创建组 for (int i = 0; i < n - gap; i+=gap)//注意不要越界 { 	int end = i;//已经排好的最后一个数字 	int tmp = a[i + gap];//要插入的数字 	while (end >= 0) 	{ 		if (a[tmp] < a[end])//如果要插入的数字比已经排好的最后一个数字小，最后一个数字向右移 		{ 			a[end + gap] = a[end]; 			end-=gap; 		} 		else 		{ 			break;//如果比它大，跳出循环插入这个位置 		} 	} 	a[end + gap] = tmp; }

这个代码的大致逻辑是与我们的插入排序很像的，只是我们的间隔不在是之前隔一个插入而是隔好几个插入。

🚈2.2对所有组完成排序

那么如何对我们每一组全部完成排序呢？在这里小赵将他们同时进行排序，对这个代码稍微改一下，就可以完成了。

int n;//n为要排序的数组的元素的数量 int gap;//以多少为间距创建组 for (int i = 0; i < n - gap; i++)//一个组的排完一个，再进入下一组//这里要注意边界，不要越界 { 	int end = i;//已经排好的最后一个数字 	int tmp = a[i + gap];//要插入的数字 	while (end >= 0) 	{ 		if (tmp < a[end])//如果要插入的数字比已经排好的最后一个数字小，最后一个数字向右移 		{ 			a[end + gap] = a[end]; 			end-=gap; 		} 		else 		{ 			break;//如果比它大，跳出循环插入这个位置 		} 	} 	a[end + gap] = tmp; }

🚢3完成希尔排序

虽然刚刚我们已经完成各个组的排序了，但是光完成间隔为二为三的组排序是不行的，我们还要最后走一次插入排序，对我们的整体数据进行一次完整排序，当然这时候可能就有人会说这样真的会快吗？各位不要急，完成了希尔排序，小赵就将为大家解开这个答案。

void ShellSort(int* a, int n) { 	int gap = n; 	while (gap > 1) 	{ 		gap = gap / 3 + 1;//多次取组//保证最后一次整体排序 		for (int i = 0; i < n - gap; i ++) 		{ 				int end = i; 				int tmp = a[i + gap]; 				while (end >= 0) 				{ 					if (tmp < a[end]) 					{ 						a[end + gap] = a[end]; 						end-=gap; 					} 					else 					{ 							break; 					} 				} 				a[end + gap] = tmp; 		}	 	} }

当然这里小赵还是忍不住多说一嘴，就是这个gap 的取值，我们为什么会取n/3，其实这也是约定俗称的，n/2的时候也是可以的。

✈4.希尔排序性能分析

上面就是希尔排序了，下面聊聊大家最关心的问题即希尔排序如何让程序变快的问题，首先从逻辑上就是小赵说的，就是整体上的一次排序，让小的都在前面，大的都在后面，这样后面进行的插入排序移动次数就会减少，那么也就是前面的排序会对后面的排序产生一个增益的效果。而其的时间复杂度究竟到底是多少，小赵找来了点资料。

根据上述的两个资料我们可以大致知道希尔排序的时间复杂度的结果，其的时间复杂度是要远远比我们的冒泡排序和插入排序快的，当然小赵为了让大家更直观的看到差距，小赵就用代码的方式，看看这些排序在处理一定数据时候的时间吧。

代码如下：

void TestOP() { 	srand(time(0)); 	const int N = 100000;//制造数据 	int* a1 = (int*)malloc(sizeof(int) * N);//开辟数组 	int* a2 = (int*)malloc(sizeof(int) * N); 	int* a3 = (int*)malloc(sizeof(int) * N);  	for (int i = 0; i < N; ++i) 	{ 		a1[i] = rand(); 		a2[i] = a1[i]; 		a3[i] = a1[i]; 	} 	int begin1 = clock();记录程序开始时间 	InsertSort(a1, N);//插入 	int end1 = clock();//结束时间  	int begin2 = clock(); 	ShellSort(a2, N);//希尔排序 	int end2 = clock();  	int begin3 = clock(); 	BubbleSort(a3, N);//冒泡排序 	int end3 = clock();  	printf("InsertSort:%d\n", end1 - begin1); 	printf("ShellSort:%d\n", end2 - begin2); 	printf("BubbleSort:%d\n", end3 - begin3);  	free(a1); 	free(a2); 	free(a3); } int main() { 	 	TestOP(); 	return 0; }

结果如下