程序员必须掌握的排序算法：希尔排序的原理与实现

鸽芷咕

发布于 2023-12-28 09:38:04

1640

发布于 2023-12-28 09:38:04

文章被收录于专栏：C++干货基地C++干货基地

? 前言

希尔排序，不知道大家有没有感觉听起来都很吊吊的样子。事实也确实如此，希尔排序的性能在八大排序中某些特定情况是最强的，也是我们必学的高效算法之一。

文章目录

? 前言
一、什么是希尔排序
二、希尔排序的思想与实现
- 2.1 希尔排序的版本一
- 2.2 希尔排序的优化版本
二、希尔排序的性能

一、什么是希尔排序

希尔排序，也称为缩小增量排序，是插入排序的一种高效改进版本也可以把它

看做为插入排序的优化版

希尔排序法的基本思想是：先选定一个整数，把待排序文件中所有记录分成个组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后，取，重复上述分组和排序的工作。当到达=1时，所有记录在统一组内排好序

二、希尔排序的思想与实现

既然希尔排序是分组来实现的，那么这样做的好处呢？其实是因为每次分组跳着来进行选择排序，可以更快的吧大数调整到后面：

而插入排序却需要需要排 N*N 次才能找到最大值（最坏情况）

如上图当排的分组的区间为2的时候每次只需要排一次就可以达到全部有序了。

2.1 希尔排序的版本一

当我们看到分组的时候肯定大部分想的都是定义一个 gap组然后再进行每次排序一直重复到 1 ；

这里需要注意的是数据被分成了 gap组那么每次进行交换
都需要间隔 gap 组

而被分成了 gap 组那么每次都需要排序gap次所以需要一个外循环

? 代码演示：

// 希尔排序
void ShellSort(int* a, int n)
{
	//方法一普通想法
	
	int gap = 3;

	for (int j = gap; j > 0; j--)
	{
		for (int i = j; i < n-j; i++)
		{
			int end = i;
			int tmp = a[end+j];
			while (end >= 0)
			{
				if (a[end] > tmp)
				{
					a[end + j] = a[end];
				}
				else
				{
					break;
				}
				end = end-j;
			}
			a[end + j] = tmp;
		}
	}
}

以上就是普通实现的希尔排序的代码了，而第二组排序的时候就是从第二个数据开始了：

所以 i = j, 而每次需要跨越 gap 个数据

2.2 希尔排序的优化版本

但是上述代码有很大的局限性，希尔排序在排序每次需要的 gap 分组都不一样：

一般我们是采用 gap = n/2
优化一下也可以写成 gap = n/3 +1

gap = n/3 +1 为什么要+1 呢因为当时候 2/3 的时候编译器回默认为 0 ，但我们这次还需要再排序一次数据所以需要+1；

? 代码演示：

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[end + gap];
			while (end >= 0)
			{
				if (a[end] > tmp)
				{
					a[end + gap] = a[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			a[end + gap] = tmp;
		}
	}

}

二、希尔排序的性能

希尔排序的特性总结：

希尔排序是对直接插入排序的优化。
当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。
希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好些树中给出的希尔排序的时间复杂度都不固定：

《数据结构(C语言版)》— 严蔚敏