排序算法第一谈：希尔排序

柔光的暖阳◎ 2023-01-01 03:37 8阅读 0赞

> 希尔排序是插入排序的一种，又称“缩小增量排序”，是插入排序算法的一种更高效的改进版本。

思想：  
将待排序数组按照步长gap进行分组，然后将每组的元素利用直接插入排序的方法进行排序；每次将gap折半减小，循环上述操作；当 gap=1时，利用直接插入，完成排序。同样的：从上面的描述中我们可以发现：希尔排序的总体实现应该由三个循环完成：第一层循环：将gap依次折半，对序列进行分组，直到gap=1第二、三层循环：也即直接插入排序所需要的两次循环。

![4263c4ada0679847c3038c962b82b7b1.png][]

## 代码 ##

**移位法**

public static void shell(int[] arr) { 
            int index = 0;//记录当前分组的元素索引
            int indexVal = 0;//元素值
            for (int gap = arr.length / 2; gap > 0; gap /= 2) { //进行分组
                for (int i = gap; i < arr.length; i++) { //对每个分组进行遍历
                    index = i;
                    indexVal = arr[i];
                    while (index - gap >= 0 && arr[index - gap] > indexVal) { 
                        arr[index] = arr[index - gap];//向后移动
                        index -= gap;//按步长向后移动
                    }
                    arr[index] = indexVal;//移动完成后，当前位置就是indexVal所需要存放的位置
                }
            }
        }
       
        /** * 交换元素 * * @param arr * @param i * @param j */
        public static void exchage(int[] arr, int i, int j) { 
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }

**交换法**

/** * 交换法 * * @param arr */
        public static void shellSoer(int[] arr) { 
            for (int gap = arr.length / 2; gap > 0; gap /= 2) { //进行分组
                //遍历每个分组
                for (int i = gap; i < arr.length; i++) { 
                    //对一个分组的元素进行排序
                    for (int j = i - gap; j >= 0; j -= gap) { 
                        if (arr[j] > arr[j + gap]) exchage(arr, j + gap, j);//满足条件进行交换
                    }
                }
            }
        }

交换法和位移法速度比较：

![image.png][]

[4263c4ada0679847c3038c962b82b7b1.png]: /images/20221120/b6fed66c49524c9aaaa7094cab0d01ad.png
[image.png]: /images/20221120/ca0fd9486b944d978dded86f767bf0d6.png