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

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

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

[img=75%,75%]https://img-blog.csdnimg.cn/img_convert/4263c4ada0679847c3038c962b82b7b1.png[/img]

代码

移位法

1.     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;    }

复制代码

互换法

1. /**     * 互换法     *     * @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);//满足条件举行互换                }            }        }    }

复制代码

互换法和位移法速度比力：

来源：https://blog.csdn.net/qq_44895397/article/details/112000060
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！