图解希尔排序的交换法和移位法

大数据记事本 2020-07-31

1173

在《图解冒泡、选择和插入排序》一篇中，我们分析了插入排序，插入排序的过程是将无序区间中的元素依次插入到有序区间中。但是，以升序排列为例，如果数值较小的元素都靠后，那么在查找插入位置时，就需要移动多个元素，从而增加排序花费的时间。

希尔排序是在插入排序的基础上优化而来的，它把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

希尔排序的实现分为交换法和移位法两种，相对交换法，移位法的效率更高，下面我们来分析这两种方法。

一、交换法

交换法是将每个组中的所有元素两两比较，不满足顺序即交换。假设有下面一组元素，采用交换法的流程如下：

①先对原始数组进行分组，增量=数组长度/2=10/2=5，下面颜色相同的元素表示同一组：

②从每组的第二个元素开始，依次和前面的所有元素比较大小，和下标为0的元素同组的第二个元素的下标为0+增量（这里用gap表示），所以从gap开始：

③这里第一组的元素分别为8和3，不满足顺序，进行交换，然后gap后移，直到遍历完所有元素，此时每个组内的元素有序：

④缩小增量为原来的一半，5/2=2，重新进行分组：

⑤重复②③步骤，使每个组内的元素有序：

⑥再次缩小增量为原来的一半，2/2=1，重新分组，此时所有的元素都在一个组内

⑦从第二个元素开始依次和前面的元素比较，不满足顺序则交换，当所有元素交换完后，即排序完成，如下图：

代码实现：

public static int[] transShellSort(int[] arr) {
        int tmp = 0;
        int len = arr.length;
        //增量从数组长度/2开始，之后每次都/2，只要得到的增量大于0，就一直循环
        for (int gap = len  2; gap > 0; gap = 2) {
            //从每组的第二个元素开始，依次和前面的所有元素比较大小，
            // 和下标为0的元素同组的第二个元素的下标为0+gap，所以从gap开始
            for (int i = gap; i < arr.length; i++) {
                //j从i的前一个元素开始，直到遍历i前面的所有同组元素
                for (int j = i - gap; j >= 0; j -= gap) {
                    //这里虽然定义j=i-gap,但这只是初始j的值，当j-=gap后这个等式便不再成立，
                    // 所以交换时不能直接将arr[j]和arr[i]的值交换
                    if (arr[j] > arr[j + gap]) {
                        tmp = arr[j];
                        arr[j] = arr[j + gap];
                        arr[j + gap] = tmp;
                    }
                }
            }
        }
        return arr;
    }

二、移位法

和交换法相比，移位法是对每个组直接进行插入排序。还是采用上面那组元素：

我们以增量缩小为2时举例，此时所有元素分为两组，分别为[3,1,0,9,7] 和 [5,6,8,4,2]

分别对两组元素直接进行插入排序，具体流程可以看《图解冒泡、选择和插入排序》中关于插入排序的讲解。

同样，当所有的元素分到一个组，即增量为1时，进行排序后的结果就是最终的排序结果。

代码实现：

public static int[] moveShellSort(int[] arr) {
        int tmp = 0;
        int len = arr.length;
        for (int gap = len / 2; gap > 0; gap /= 2) {
            //从第gap个元素开始，逐个对其所在的组进行直接插入排序
            for (int i = gap; i < len; i++) {
                int j = i;
                //这里的tmp就相当于插入排序中的insertVal，而j-gap就相当于insertIndex
                tmp = arr[j];
                //gap所在的组，前面的数如果大于待插入的数，那么表示没有找到插入位置，
                // 其中arr[j]和arr[j-gap]为同组相邻的两个数
                if (arr[j] < arr[j - gap]) {
                    while (j - gap >= 0 && arr[j - gap] > tmp) {
                        arr[j] = arr[j - gap];
                        //下标前移量为步长
                        j -= gap;
                    }
                    //当跳出while循环时，表示找到了插入位置
                    //当j-gap小于0时，tmp的位置下标就是j-gap+gap=j
                    arr[j] = tmp;
                }
            }
        }
        return arr;
    }

数据库

文章转载自大数据记事本，如果涉嫌侵权，请发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。

图解希尔排序的交换法和移位法

评论