【排序】3.希尔排序法
希尔排序（直接插入排序的优化）
1.分组思想
上图中gap为5，说明要分成5组。
这5组分别用了五种颜色的线条连接起来了。
第1组：9、4
第2组：1、8
第3组：2、6
第4组：5、3
第5组：7、5
2.缩小增量的过程
前面gap为5的情况排序后会变成下面情况
按照gap把数据分成了两组。
当数据很大的时候，数据的间隔很大。
小的数据会往前方，大的数据会往后放。
gap会逐渐缩小，间隔也会逐渐缩小。
整体的数据会更加趋于有序，这个时候使用直接插入排序效率会更高。
gap为2的时候会排序成下面情况
此时分为了1组，再排序一次后变成下面情况
此时的数据即为有序的。
3.排序情况分析
3.1 排序五组数据的情况
-
gap为5，将数据分为5组，图中红色线画中的为第一组。定义一个 i 变量指向这一组的第二个数据，定义一个 j 变量指向 i - gap 的位置。
-
将 i 下标的值放到定义的 tmp 中，然后与 j下标 的值比较。
若 j 下标的值较大，将 j 下标的值放到 j + gap 的位置。
执行后：
-
j 变量向 j - gap 位置走，若这个位置的下标为负数。
则要将 tmp 的值放到 j + gap的位置。
j 变量此时在-5下标处，要将 tmp 的值放到 j + 5的位置。
这一组数据此时为有序了。
排序下一组数据，i++即可，j 变量依然是在 i - gap 的位置。
后面4组数据类似，不在演示。
最终排序结果是：
3.2 排序两组数据的情况
- 此时 gap 为2，数据此时分为了两组。第一组由红色线画出（4、2、5、8、5），第二组由蓝色线画出（1、3、9、6、7）。
i 变量指向这一组的第二个数据， j 变量指向 i - gap 的位置。
- 将 i 下标的值放到定义的 tmp 中，然后与 j下标 的值比较。
若 j 下标的值较大，将 j 下标的值放到 j + gap 的位置。
执行后：
- j 变量向 j - gap 位置走，若这个位置的下标为负数。
则要将 tmp 的值放到 j + gap的位置。
j 变量此时在-2下标处，要将 tmp 的值放到 j + 2的位置。
这一组数据中的 2 和 4 此时为有序了。
排序下一组数据，i++ 即可，j 变量依然是在 i - gap 的位置。
后面剩下的数据类似，不在演示。
最终排序结果是：
3.3 排序一组数据的情况
- i 变量指向第二个数据， j 变量指向 i - gap 的位置。
- 将 i 下标的值放到定义的 tmp 中，然后与 j下标 的值比较。
若 j 下标的值较大，将 j 下标的值放到 j + gap 的位置。
执行后：
- j 变量向 j - gap 位置走，若这个位置的下标为负数。
则要将 tmp 的值放到 j + gap的位置。
j 变量此时在-1下标处，要将 tmp 的值放到 j + 1的位置。
此时 前两个数据有序了，后面的数据排序过程类似。
排序下一组数据，i++ 即可，j 变量依然是在 i - gap 的位置。
最终结果是：
4.代码分析以及实现
1.间隔分组，通常为总长度的一半
2.组内排序
3.重新设置间隔分组，为前一组的一半
4.当gap= 1时,为直接插入排序。
void ShellSort(int *arr, int n)
{
// 初始化间隔为数组的长度
int gap = n;
while (gap > 1)
{
// 逐渐减小间隔，每次将间隔除以2
gap /= 2;
// 也可以使用这种方式来减小间隔，这是一种不同的策略
// gap = gap / 3 + 1;
// 遍历数组，每次跳过gap个元素，对每个子序列进行插入排序
for (int i = 0; i < n - gap; i++)
{
// 初始化j为当前元素的索引
int j = i;
// 保存当前子序列的元素，以便在排序过程中移动
int tmp = arr[i + gap];
// 将tmp插入到已排序的子序列中的正确位置
while (j >= 0)
{
// 如果tmp小于子序列中的元素，则将该元素向后移动一个间隔
if (tmp < arr[j])
{
arr[j + gap] = arr[j];
// 继续向前比较
j -= gap;
}
else
{
// 如果tmp不小于子序列中的元素，则跳出循环
break;
}
}
// 当j为负数时，表示tmp已经找到了正确的位置，将其插入到子序列中
arr[j + gap] = tmp;
}
}
}
执行结果：
5.性能分析
