详细分析希尔排序(附图)

1.希尔排序思路。

希尔排序是一种基于插入排序的算法，将原始数据分成几个子序列，然后将子序列插入排序，子序列的间隔࿰逐渐减小c;最后，插入整个序列进行排序。
 。

1.直接插入分组排序，目标接近秩序-----------gap>1。

2.直接插入排序，目标有序-----------------------gap=1。

2.分组排序思路分析。

假设固定gap=3，以下数组可分为三组。

每组使用直接插入排序，使数据有序。

最后三组排好后，数组变成了：2、1、4、3、6、5、7、8，结果接近有序。

此时只需再次调用插入排序，可以使整个数组有序。

让我们来实现这一点。

2.1思维代码。

void ShellSort(int* a, int n){ 	int gap = 3;	for (int j = 0; j < gap; j++)	{ 		for (int i = j; i < n - gap; i += gap)		{ 			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;		}		for (int i = 0; i < n; i++)		{ 			printf("%d ", a[i]);		}		printf("\n");	}}。

每组排序后打印观察。

每组排序后打印观察以下是针对的 。ShellSort。

 代码外写函数的详细说明，有助于理解希尔排序算法逻辑和该函数实现的每个代码的作用：

1. 函数功能说明。ShellSort。 函数的目的是实现希尔排序算法，用于对给定的整数数组进行排序。希尔排序是一种改进的插入排序算法，插入排序࿰，将原始数据分成多个间隔的子序列c;间隔逐渐缩小，#xff0c;最后的间隔是 。1。

 完成整个数组的有序排列，与普通插入排序相比，#xff00c;在某些情况下，它可以减少元素的移动次数，提高排序效率。

• 2. 参数说明。int* a。
• ：这是指向整数类型的指针，用于接收待排序的整数组，通过这个指针，数组元素࿰可以在函数内部操作c;对数组进行排序。int n。：表示待排序数组 。a。

 元素数，函数需要知道数组的大小来正确地遍历和处理数组中的每个元素。

3. 解释代码逻辑注释。3.1 间隔 。gap。

 的初始化。

int gap = 3;这里定义并初始化为 。3。 的变量 。gap。，它代表了希尔排序中每个组的间隔。初始设置相对较大的间隔，根据这个间隔，将数组划分为多个子序列进行排序操作c;这个间隔在排序过程中会逐渐缩小，直到最后变成 。1。，这意味着进行常规的插入排序，以确保整个数组完全有序。然而，在更优化的希尔排名实现中，gap。 通常按照特定的顺序（如 。Hibbard。 序列、。Knuth。 #xff09;取值并动态变化，这里简单取固定值 。3。

 只是为了展示算法的基本思路。3.2 外层 。for。

 循环。

for (int j = 0; j < gap; j++)。这是外层的 。for。 循环，根据不同的起始位置，它根据当前的间隔控制 。gap。 子序列的数量和处理轮。循环会执行 。gap。 二次，每次以不同的起始索引开始对应处理子序列（起始索引从 。0 到 。gap - 1。

），这样，基于当前间隔划分的所有子序列都可以对整个数组进行排序。3.3 中层 。for。

 循环。

for (int i = j; i < n - gap; i += gap)。这是中层的 。for。 循环，嵌套在外循环内部，用于遍历每一个以 。j。 起始索引（#xff09由外循环控制;、间隔为 。gap。 子序列中的元素（除了最后的缺点 。gap。 个元素部分）。每次循环变量 。i。 按照间隔 。gap。

 增加，因此，您可以访问子序列中的每个元素，后续插入排序操作方便各子序列。

2.2结果显示。

3.设置gap。
当gap > 1点是预排序，目的是使数组更接近有序。当gap == 1点，数组接近有序，这样会很快。总的来说，，能达到优化效果。实现后，我们可以对性能测试进行比较。

 。

当我们不再固定gap，而是让他改变时，，下图gap=gap/2；

3.1动图演示。

现在一般认为gapɣgap/3+1更适合，让我们来实现代码。

3.2实现最终代码。

这里省去了一层for循环，将原来的一组交换成一组交换，时间的复杂性没有改变。

//升序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] > a[end + gap]) { a[end + gap] = a[end]; end -= gap; } else { break; } } a[end + gap] = tmp; } }}。

4.时间复杂。

4.时间复杂度

记忆：O(N^1.3)。