希尔排序----附图解（C语言）

目录

一、简介

二、代码部分 

2.1完整代码

2.2代码输出结果 

三、代码部分分析

 3.1核心代码

3.2代码运行部分的过程（附图解） 

四、总结 

---

一、简介

中文名：希尔排序

英文名：Shell's Sort

别名：缩小增量排序

时间复杂度：O（1）

稳定性：不稳定的排序算法

原理：希尔排序是把整个数组元素按下标的一定增量分组，对每组分别使用直接插入排序算法排序；随着增量逐渐减少，每组包含的元素越来越多，当增量减至 1 时，整个数组恰被分成一组，算法便终止，排序完成。

 

二、代码部分  2.1完整代码

void ShellSort(int* arr, int flag)
{
	int tap = flag;    //设置排序每组的增量
	while (tap > 1)
	{
		tap = tap / 2;   //（每次每组的增量）

		for (int i = 0; i < flag - tap; i++)//一组一个轮流排
		{
			int end = i;
			int label = arr[end + tap];
			while (end >= 0)
			{
				if (label < arr[end])
				{
					arr[end + tap] = arr[end];
					end -= tap;
				}
				else
				{
					break;
				}
			}
			arr[end + tap] = label;
		}
	}
}

int main()
{
	int arr[10] = {8,5,4,2,9,1,0,3,7,6};
	printf("排列前：");
	for (int i = 0; i < 10; i++)
	{
		printf("%d  ", arr[i]);
	}
	printf("\n\n");

	int flag = sizeof(arr) / sizeof(arr[1]);   
	ShellSort(arr, flag);

	printf("排列后：");
	for (int i = 0; i < 10; i++)
	{
		printf("%d  ", arr[i]);
	}
	printf("\n\n");
	return 0;
}

 

2.2代码输出结果 

 

三、代码部分分析  3.1核心代码

void ShellSort(int* arr, int flag)
{
	int tap = flag;    //设置排序每组的增量
	while (tap > 1)
	{
		tap = tap / 2;   //（每次每组的增量）

		for (int i = 0; i < flag - tap; i++)//一组一个轮流排
		{
			int end = i;
			int label = arr[end + tap];
			while (end >= 0)
			{
				if (label < arr[end])
				{
					arr[end + tap] = arr[end];
					end -= tap;
				}
				else
				{
					break;
				}
			}
			arr[end + tap] = label;
		}
	}
}

 

      整个希尔排序的过程可看作为，将数组元素每次按照一定的增量进行分组，再对每个组进行插入排序。

       tap = tap / 2；我们将数组元素的一半作为，第一次排列的增量，而后的每一次增量都为上一次增量的一半。

3.2代码运行部分的过程（附图解） 

      首先让我们看原数组（如下图）：

 

      在数组元素中，一共有10个元素，所以第一次的增量 tag = 10 / 2 = 5；因此我们可以将数组分成以下五个部分：①arr[0]、arr[5] ；②arr[1]、arr[6]；③arr[2]、arr[7]；④arr[3]、arr[8]；⑤arr[4]、arr[9]。即数组元素{8，1}、{5，0}、{4，3}、{2，7}、{9，6}五部分（如下图）。

 

      然后再将这五组分别进行直接插入排序，最终利用得到如下结果： 

 

       而后第二次的增量 tag = 5 / 2 = 2；因此我们可以将数组分成以下两个部分：①arr[0]、arr[2] 、arr[4]、arr[6]、arr[8]；②arr[1]、arr[3]、arr[5]、arr[7]、arr[9；]即数组元素{1，3，6，5，7}、{0，2，8，4，9}；两个部分（如下图）。

 

      然后再将这两组分别进行直接插入排序，最终利用得到如下结果：  

 

       而后第三次的增量 tag = 2 / 2 = 1；因此我们再将数组进行一次直接插入排序，即可，最后得出以下结果（排列结束）：

四、总结 

希尔排序的优缺点

优点：不需要大量的辅助空间，当刚开始元素无序的时候，步长最大，所以插入排序的元素个数很少，速度很快；当元素基本有序了，步长很小，插入排序对于有序的序列效率很高。代码简单，容易实现。

缺点：对规模非常大的数据希尔排序不是最优选择。

 最后到这里，文章就结束了，如果在内容上有问题，恳请各位大佬指出。