Tim

一枚野生程序员~

  • 主页
  • 分类
  • 标签
  • 归档
  • 关于
所有文章 工具

Tim

一枚野生程序员~

  • 主页
  • 分类
  • 标签
  • 归档
  • 关于

插入排序的优化之希尔排序

阅读数:次 2020-04-09
字数统计: 714字   |   阅读时长≈ 2分

希尔排序是插入排序的一种,又称缩小增量排序,是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法,可以说它是插入排序的高级版。我们可以先回顾一下直接插入排序的过程:

排序前将第一个元素看成有序的数列

  • 第1趟排序后:得到一个长度为2的有序数列
  • 第2趟排序后:得到一个长度为3的有序数列
  • 第3趟排序后:得到一个长度为4的有序数列
  • ……..每趟插入排序,都可以将一个无序值插入一个有序数列,直到全部元素有序

最坏情况下,直接插入排序的时间复杂度是O(n²)。从上图可以看出,6这个元素被移动了三次才到末尾。我在直接插入排序的博客《O(n²)的三个排序算法》中写到,直接插入排序最好的情况就是本来就有序,所以直接插入排序用来排序那些近乎有序的数组是非常适合的。所以我们对于一个无序数组,先把它变成大致有序,然后超级大致有序,然后变成超级超级大致有序……最后变成完全有序,这样可以省略掉很多不必要的元素交换。

那么如何让大元素一开始就分批向后移动呢?那就是通过分组排序的方式, 应该怎么分呢?比如有10个元素的序列,分成几个才合适?每次缩减又是多少呢? 将一个序列分成好几个序列,用一个数来表示:那个数称为增量,我们可以发现增量越来越小,其实就是数组越来越有序的过程。

下面来看看希尔排序的过程:

mark

下面通过代码来实现一下希尔排序:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public static void shellSort(int[] arr){
//每次都缩小增量
for (int step = arr.length / 2; step > 0; step /= 2) {
for (int i = step; i < arr.length; i++) {
int j = i;
int tmp = arr[j];
//注意这里不是结构上的前一个元素,而是对于组而言的,同组之间的元素交换
while(j - step >= 0 && arr[j - step] > tmp){
arr[j] = arr[j - step];
j = j - step;
}
arr[j] = tmp;
}
}
}

希尔排序和直接插入排序的对比,对30万个随机数进行排序

mark

最后再思考一个问题,希尔排序是稳定排序吗?

当然不是,因为通过上面的结论我们知道,希尔排序是依靠分组来进行排序的,值相同的元素完全有可能被调换位置,所以希尔排序是一个不稳定排序。

赏

谢谢你请我喝咖啡

支付宝
微信
  • 本文作者: Tim
  • 本文链接: https://zouchanglin.cn/4284449870.html
  • 版权声明: 本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 许可协议。转载请注明出处!
  • 排序算法
  • 数据结构与算法

扫一扫,分享到微信

O(nLogn)的归并排序
O(n²)的三个排序算法
目录,不存在的…
© 2017-2021 Tim
本站总访问量次 | 本站访客数人
  • 所有文章
  • 工具

tag:

  • 生活
  • Android
  • 索引
  • MySQL
  • 组件通信
  • Nginx
  • JavaSE
  • JUC
  • JavaWeb
  • 模板引擎
  • 前端
  • Linux
  • 计算机网络
  • Docker
  • C/C++
  • JVM
  • 上传下载
  • JavaEE
  • SpringCloud
  • Golang
  • Gradle
  • 网络安全
  • 非对称加密
  • IDEA
  • SpringBoot
  • Jenkins
  • 字符串
  • vim
  • 存储
  • 文件下载
  • Mac
  • Windows
  • NIO
  • RPC
  • 集群
  • 微服务
  • SSH
  • 配置中心
  • XML
  • Chrome
  • 压力测试
  • Git
  • 博客
  • 概率论
  • 排序算法
  • 分布式
  • 异常处理
  • 文件系统
  • 哈希
  • openCV
  • 栈
  • 回溯
  • SpringCore
  • 流媒体
  • rtmp
  • 面向对象
  • Vue
  • ElementUI
  • 软件工程
  • 异步
  • 自定义UI
  • ORM框架
  • 模块化
  • 交互式
  • Jsoup
  • Http Client
  • LRUCache
  • RabbitMQ
  • 消息通信
  • 服务解耦
  • 负载均衡
  • 权限
  • 多线程
  • 单例模式
  • Protobuf
  • 序列化
  • Python
  • m3u8
  • 堆
  • 二叉树
  • 自定义View
  • 观察者模式
  • 设计模式
  • 线程池
  • 动态扩容
  • 高可用
  • GC
  • ffmpeg
  • SpringMVC
  • REST
  • Redis
  • 缓存中间件
  • UML
  • Maven
  • Netty
  • 高性能网络
  • IPC通信
  • IO
  • Stream
  • 发布订阅
  • SQLite
  • Hash
  • 集合框架
  • 链表
  • Lambda
  • 汇编语言
  • 组件化
  • Router
  • 开发工具

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录(注意不是yilia-plus根目录)执行以下命令:
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置:

      jsonContent:
        meta: false
        pages: false
        posts:
          title: true
          date: true
          path: true
          text: false
          raw: false
          content: false
          slug: false
          updated: false
          comments: false
          link: false
          permalink: false
          excerpt: false
          categories: false
          tags: true
    

  • 思维导图
  • PDF工具
  • 无损放大
  • 代码转图
  • HTTPS证书