希尔排序（C#）

目录

 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);
       
        }

运行结果：