排序算法-希尔排序

上一篇讲解了简单插入排序算法,以及在其基础上优化的二分插入排序算法,但是每次插入需要按间隔为 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)\)。

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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏xingoo, 一个梦想做发明家的程序员

剑指OFFER之调整数组顺序使奇数位于偶数前面找(九度OJ1516)

题目描述: 输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有的奇数位于数组的前半部分,所有的偶数位于位于数组的后半部分,并保证奇数和奇数,偶数和...

2276
来自专栏xiaoxi666的专栏

今日头条笔试题:“最小数字*区间和”的最大值【单调栈】

  利用单调栈,从前向后和从后向前分别遍历一遍数组,得到每个元素的左边界和右边界(边界的定义即为碰到比该元素更小的即停止),最后用每个元素乘以每个元素对应的区间...

3101
来自专栏Python小屋

Python版堆排序算法

其他排序算法的Python实现请参考:Python版归并排序算法(附Python程序__name__属性用法演示视频),侏儒排序算法原理与Python实现,Py...

3375
来自专栏分布式系统和大数据处理

正则表达式教程

1085
来自专栏java工会

java冒泡排序和快速排序

3383
来自专栏蜉蝣禅修之道

算法考试填数字问题

2062
来自专栏和蔼的张星的图像处理专栏

488. 快乐数

一个数是不是快乐是这么定义的:对于一个正整数,每一次将该数替换为他每个位置上的数字的平方和,然后重复这个过程直到这个数变为1,或是无限循环但始终变不到1。如果可...

1583
来自专栏数据结构与算法

洛谷P3357 最长k可重线段集问题(费用流)

题目描述http://www.cnblogs.com/zwfymqz/p/8559566.html 给定平面 x-O-yx−O−y 上 nn 个开线段组成的集合...

4136
来自专栏计算机视觉与深度学习基础

Leetcode 31 Next Permutation

Implement next permutation, which rearranges numbers into the lexicographically...

2065
来自专栏黑泽君的专栏

java基础学习_基础语法(下)02_day06总结

============================================================================= ==...

611

扫码关注云+社区

领取腾讯云代金券