排序算法-希尔排序

上一篇讲解了简单插入排序算法,以及在其基础上优化的二分插入排序算法,但是每次插入需要按间隔为 1 移动有序区的元素,效率不高,下面我们来介绍一种新的插入排序算法-希尔排序。

算法简介

希尔排序(Shell Sort),也称递减增量排序算法,是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法
希尔排序通过将比较的全部元素分为几个区域来提升插入排序的性能。这样可以让一个元素可以一次性地朝最终位置前进一大步。然后算法再取越来越小的步长进行排序,算法的最后一步就是普通的插入排序,但是到了这步,需排序的数据几乎是已排好的了(因为直接插入排序在元素基本有序的情况下,效率是很高的)。

算法描述

  • 先将要排序的一组数按某个增量d(n/2,n为要排序数的个数)分成若干组,每组中记录的下标相差d。
  • 对每组中全部元素进行直接插入排序,然后再用一个较小的增量(d/2)对它进行分组,在每组中再进行直接插入排序。
  • 当增量减到1时,进行直接插入排序后,排序完成。

代码实现

/**
     * 希尔排序
     *
     * @param array
     */
    private static void shellSort(int[] array) {
        if (array == null || array.length == 0 || array.length == 1)
            return;
        int gap = array.length / 2;
        while (gap > 0) {// 逐渐减小gap,最终为1,进行直接插入排序
            for (int i = 0; i < gap; i++) {// 排序第i组,每一组内部进行插入排序
                for (int j = gap + i; j < array.length; j += gap) {// 直接插入排序的间隔1变为gap即可
                    int index = j;
                    int insertVal = array[j];
                    while (index > gap - 1 && insertVal < array[index - gap]) {
                        array[index] = array[index - gap];
                        index -= gap;
                    }
                    array[index] = insertVal;//放置insertVal
                }
            }
            gap = gap >> 1;
        }
    }

性能分析

希尔排序的时间复杂度是和所取的序列增量有关。希尔排序的时间复杂度分析较为复杂。下面直接给出结论。

本文选用的就是常用的Shell增量序列,Shell增量序列的最坏时间复杂度为(O(n^2))。

Hibbard增序序列最坏时间复杂度为(O(n^{3/2})),平均时间复杂度约为(O(n^{5/4}))。

Sedgewick增量序列的最坏时间复杂度为(O(n^{4/3}));平均时间复杂度约为(O(n^{7/6}))。

空间复杂度都是(O(1))。

希尔排序会破坏元素间相互位置,因此希尔排序是不稳定的。

全部评论

相关推荐

吐泡泡的咸鱼:我也工作了几年了,也陆陆续续面试过不少人,就简历来说,第一眼学历不太够,你只能靠你的实习或者论文或者项目经历,然后你没有论文,没有含金量高的比赛和奖项,只能看实习和项目,实习来说,你写的实习经历完全不清楚你想找什么工作?行研?数据分析?且写的太少了,再看项目,这些项目先不说上过大学读过研究生的都知道很水,然后对你想找的岗位有什么帮助呢?项目和实习也完全不匹配啊,你好像在努力将你所有的经历都放在简历里想表现你的优秀,但是对于你想找的岗位来说,有什么用呢?最后只能获得岗位不匹配的评价。所以你需要明白你想要找的岗位要求是什么,是做什么的,比如产品经理,然后再看你的经历里有什么匹配的上这个岗位,或者对这个岗位以及这个岗位所在的公司有价值,再写到你的简历上
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务