【排序算法】希尔排序-Toy模板网

这篇具有很好参考价值的文章主要介绍了【排序算法】希尔排序。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

【排序算法】希尔排序,排序算法,排序算法,算法,数据结构,希尔排序,C语言

📝希尔排序( 缩小增量排序 )

希尔排序是一种经典的排序算法，它通过多次插入排序的方式，以及逐步缩小增量的策略，实现对数据的高效排序，希尔排序法又称缩小增量法。

🌠分组思想

希尔排序的核心思想在于将待排序的数据分成若干组，对每一组数据进行插入排序。这样做的好处是，一方面可以减少数据的比较次数和移动次数，另一方面可以利用已经部分有序的性质，加速排序的过程。初始时，数据被分成的组数由一个称为增量的值决定。

🌠缩小增量的过程

希尔排序的另一个关键点是逐步缩小增量的过程。初始时，增量的值通常为数组长度的一半。随着排序的进行，增量逐步减小，直到增量为1，完成最后一次排序。这样的设计可以使得排序过程更加高效，因为随着增量的减小，每次排序所需要的数据交换次数会逐渐减少。

🌠 排序步骤

希尔排序的排序步骤可以分为以下几个阶段：

分组排序：初始时，根据设定的增量将数据分成若干组，对每组数据进行插入排序，使得每组数据都部分有序。
逐步缩小增量：在每一轮排序后，逐步减小增量的值，重新分组并进行插入排序，直到增量为1。
最后一次排序：当增量为1时，整个数组被视为一组，对整个数组进行插入排序，使得整个数组有序。

图解：
【排序算法】希尔排序,排序算法,排序算法,算法,数据结构,希尔排序,C语言

代码实现：

// 预排序  -- 目标：接近有序  gap > 1
// 插入排序  -- 目标：有序    gap == 1
// O(N^1.3)
void ShellSort(int* a, int n)
{
	int gap = n;
	while (gap > 1)
	{
		//gap /= 2;
		gap = gap/3 + 1;

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

			a[end + gap] = tmp;
		}

	}
}