目录
1 什么是希尔排序
2 算法步骤
3 代码实现
1 什么是希尔排序
希尔排序是插入排序的一种更高效的改进版本，也称为缩小增量排序。它的基本思想是将原始数据分成多个子序列来进行插入排序，通过逐渐缩小子序列的间隔（增量），最终完成整个数组的排序。(学习本篇前先掌握插入排序）
与普通插入排序不同，希尔排序在排序初期允许元素进行较大距离的交换，这样可以快速将元素移动到接近其最终位置的地方，从而减少后续插入排序时的比较和移动次数，提高排序效率。
2 算法步骤
- 选择增量序列：选择一个初始增量，通常可以将数组长度的一半作为初始增量，后续不断将增量缩小，直到增量为 1。（结束条件是步长<=0)
- 按增量进行分组插入排序：根据当前增量将数组分成若干个子序列，对每个子序列分别进行插入排序。
- 缩小增量：将增量缩小，重复上一个步骤 ，直到增量为 1，此时整个数组就完成了排序。(之后的每一次都是在上一次步长的基础上/2)
3 代码实现
我们分析希尔排序具体的排序方法是使用插入排序，基本原理是设置步长，然后不断缩小步长，直到步长为1时排序结束。
套路写法：一层获得步长，一层获取未排序区的元素，一层将内容插入到合适的位置。（以下代码的运行环境为unity2022,可供参考）
private void Test(){int[] arr ={ 8, 7, 1, 5, 4, 2, 6, 3, 9 };//确定步长//基本规则：每次步长变化都是/2//一开始步长 就是数组的长度/2//之后每一次 都是在上一次的步长基础上/2//结束条件是步长<=0//第三步 执行插入排序for(var step = arr.Length / 2; step > 0; step /= 2){//实现插入排序for (var i = step; i < arr.Length; i++){var noSortNum = arr[i];var sortIndex = i - step;while (sortIndex >= 0 && arr[sortIndex] > noSortNum){arr[sortIndex + step] = arr[sortIndex];sortIndex-=step;}arr[sortIndex + step] = noSortNum;}}foreach (var value in arr)Debug.Log(value);}运行结果：
