[数据结构与算法]希尔排序java实现

?
?

活动地址：CSDN21天学习挑战赛

学习的最大理由是想摆脱平庸，早一天就多一份人生的精彩；迟一天就多一天平庸的困扰。各位小伙伴，如果您：
想系统/深入学习某技术知识点…
一个人摸索学习很难坚持，想组团高效学习…
想写博客但无从下手，急需写作干货注入能量…
热爱写作，愿意让自己成为更好的人…
…

希尔排序

可以看作是一种特殊的插入排序，通过“分组”的方式减少逆序对，从而达到减少时间复杂度的目的

排序函数：void sort(int[] nums)

选择排序：void sort(int[] nums, Integer step)

合并操作：List<Integer> getStepSequence(int[] nums,int max)

算法分析

希尔排序（Shell Sort）又称为缩小增量排序，输入插入排序算法，是对直接排序算法的一种改进。本文介绍希尔排序算法。
对于插入排序算法来说，如果原来的数据就是有序的，那么数据就不需要移动，而插入排序算法的效率主要消耗在数据的移动中。因此可知：如果数据的本身就是有序的或者本身基本有序，那么效率就会得到提高。
希尔排序的基本思想是：将需要排序的序列划分成为若干个较小的子序列，对子序列进行插入排序，通过则插入排序能够使得原来序列成为基本有序。这样通过对较小的序列进行插入排序，然后对基本有序的数列进行插入排序，能够提高插入排序算法的效率。
在希尔排序中首先解决的是子序列的选择问题。对于子序列的构成不是简单的分段，而是采取相隔某个增量的数据组成一个序列。一般的选择原则是：去上一个增量的一般作为此次序列的划分增量。首次选择序列长度的一般为增量。
其过程大致如下：
过程如下：

1. 选择一个增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1；

2. 按增量序列个数 k，对序列进行 k 趟排序；

3. 每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

算法实现

    /**
     * 子类需要实现的核心排序算法
     */
    @Override
    protected void sort() {
        List<Integer> stepSequence = getStepSequence(nums.length);
        for (int i = stepSequence.size() - 1; i >= 0; i--) {
            sort(stepSequence.get(i));
        }
    }

    /**
     * 对列表进行选择排序，步长为step
     */
    private void sort(int[] nums,Integer step) {
        // 进行step次竖向希尔排序
        for (int col = 0; col < step; col++) {
            // 具体每一次希尔排序
            for (int begin = col + step; begin < nums.length; begin += step) {
               for (int cur = begin; cur > col; cur -= step) {
                   if (nums[cur] < data[cur - step]) {
                       swap(cur, cur - step);
                   } else {
                       break;
                   }
               }
            }
        }
    }

    /**
     * 获取步长序列，有多种实现，这里使用的最初的一中实现（希尔本人给出的步长序列）
     */
    private List<Integer> getStepSequence(int max) {
        List<Integer> stepSequence = new ArrayList<>();
        while ((max >>= 1) > 0) {
            stepSequence.add(max);
        }
        return stepSequence;
    }

复杂度分析

• 时间复杂度：根具体的序列实现有关
• 空间复杂度：没有新的空间引入，O(1)