文档章节

希尔排序

此鱼不得水
 此鱼不得水
发布于 2016/03/17 13:17
字数 328
阅读 38
收藏 0

希尔排序是以插入排序为基础的排序算法,搞懂了插入排序之后再来看希尔排序就十分简单了。

public static void sort(int[] array) {
    if(array == null || array.length <= 1) return;
    int length = array.length;
    //i用来控制每次排序的前后数的间隔
    for (int i = length / 2; i > 0; i /= 2) {
        for (int j = i; j < length; j++) {
            //下面是插入排序的步骤
            int temp = array[j];
            int k = j;
            while (k >= i && temp < array[k - i]) {
                array[k] = array[k - i];
                k -= i;
            }
            array[k] = temp;
        }
    }
}


最优时间复杂度:O(n)

平均时间复杂度:O(n^1.3)

最坏时间复杂度:O(n^2)

平均空间复杂度:O(1)

希尔排序可以通过对于排序前后间隔的值控制来做到最优化结构,最优化的结构为:

public static void sort(int[] array) {
    int out, in, temp;
    int length = array.length;
    int h = 1;
    if (h < length / 3) {
        h = 3 * h + 1;
    }

    while (h > 0) {
        for (out = h; out < length; out++) {
            temp = array[out];
            in = out;
            while (in >= h && array[in - h] > temp) {
                array[in] = array[in - h];
                in -= h;
            }
            array[in] = temp;
        }
        h = (h - 1) / 3;
    }
}

算法的思想是一样的,但是对于结构的控制可能有所不同。

希尔排序因为前后间隔值的变化可能会导致相同的元素出现位置错乱,所以也是不稳定的。

© 著作权归作者所有

共有 人打赏支持
上一篇: 快速排序
下一篇: 插入排序
此鱼不得水
粉丝 2
博文 41
码字总数 23991
作品 0
洛阳
私信 提问

暂无文章

大数据剖析热点新闻:996、巴黎圣母院、奔驰维权为什么成为本周热搜

智能大数据专家表示:每一段重要的时期都会有一串隐秘的数字密码,请往下看: 本周共有50条新闻,作为嗅嗅的样本进行数据分析,得出以下统计图: 1.新闻热词折线统计图 在新闻标题及正文中,...

forespider
18分钟前
0
0
Coding and Paper Letter(六十四)

资源整理。 1 Coding: 1.交互式瓦片编辑器。 tile playground 2.R语言包autokeras,autokeras的R接口。autokeras是一个开源的自动机器学习的软件。 autokeras 3.斯坦福网络分析平台,用于网络...

胖胖雕
55分钟前
1
0
最简单的cd命令是个大坑!

BASH Shell 是大多 Linux 发行版的默认 shell,BASH 有一些自己的内置命令,cd 就是其中的一个。 在centos6里面,系统中不存在 cd 的二进制文件。但是你仍然可以运行该命令,这是因为 cd 是 ...

gaolongquan
今天
1
0
spring获取bean的几种方式

使用jdk:1.8、maven:3.3.3 spring获取Bean的方式 pom.xml文件内容: <?xml version="1.0" encoding="UTF-8"?><project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="......

Vincent-Duan
今天
2
0
一段话系列-Linux中IO的同步、异步、阻塞、非阻塞

首先我们框定一下背景,我们探讨的是Linux系统下的IO模型。 同步和异步是针对内核操作数据而言的,同步是指内核串行顺序操作数据,异步是指内核并行(或并发)操作数据,然后通过回调的方式通...

EasyProgramming
今天
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部