「排序算法」专题 11:希尔排序(不建议多花时间了解)


「排序算法」专题 11:希尔排序(不建议多花时间了解)

希尔排序的参考资料是《算法 4》。

  • 思想来源:插入排序的优化。在插入排序里,如果靠后的数字较小,它来到前面就得交换多次。「希尔排序」改进了这种做法。带间隔地使用插入排序,直到最后「间隔」为 $1$ 的时候,就是标准的「插入排序」,此时数组里的元素已经「几乎有序」了;
  • 希尔排序的「间隔序列」其实是一个超参数,这方面有一些研究成果,有兴趣的朋友可以了解一下,但是如果这是面向笔试面试,就不用了解了。

参考代码 6

public class Solution {

    // 希尔排序

    public int[] sortArray(int[] nums) {
        int len = nums.length;
        int h = 1;

        // 使用 Knuth 增量序列
        // 找增量的最大值
        while (3 * h + 1 < len) {
            h = 3 * h + 1;
        }

        while (h >= 1) {
            // insertion sort
            for (int i = h; i < len; i++) {
                insertionForDelta(nums, h, i);
            }
            h = h / 3;
        }
        return nums;
    }

    /**
     * 将 nums[i] 插入到对应分组的正确位置上,其实就是将原来 1 的部分改成 gap
     *
     * @param nums
     * @param gap
     * @param i
     */
    private void insertionForDelta(int[] nums, int gap, int i) {
        int temp = nums[i];
        int j = i;
        // 注意:这里 j >= deta 的原因
        while (j >= gap && nums[j - gap] > temp) {
            nums[j] = nums[j - gap];
            j -= gap;
        }
        nums[j] = temp;
    }
}

希尔排序的时间复杂度至今还没有明确的结论,只有一个范围,已经不在我能介绍的范围了。

(本节完)


文章作者: liweiwei419
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 liweiwei419 !
评论
 上一篇
「排序算法」专题 12:计数排序 「排序算法」专题 12:计数排序
「排序算法」专题 12:计数排序3 种「非比较」的排序算法(了解,如果是面向笔试,不要花时间去研究)特别说明:这部分算法不建议花太多去仔细研究它们的细节。如果是面向面试,了解思想即可,用到了再学。 直接放弃我个人觉得完全可以。 学习资料是《
下一篇 
「排序算法」专题 10:冒泡排序(了解) 「排序算法」专题 10:冒泡排序(了解)
「排序算法」专题 10:冒泡排序(了解)冒泡排序(了解)前面的选择排序可以作为排序算法的入门算法,插入排序让我们看到了如何改进算法,充分利用每一轮循环的比较来加快排序的速度。冒泡排序的思想如同它的名字一样,每一轮都将一个元素「冒泡」到数组的
  目录