当前位置: 首页 > news >正文

数据结构-希尔排序(ShellSort)笔记

看动画理解

【数据结构】八大排序(超详解+附动图+源码)_数据结构排序-CSDN博客

一  基本思想

先选定一个整数gap,把待排序文件中所有记录分成gap个组,所有距离为gap的记录分在同一组内,并对每一组内的元素进行排序。

然后将gap逐渐减小重复上述分组和排序的工作。

当到达gap=1时,所有元素在统一组内排好序。

二  代码实现

import java.util.Arrays; // 导入Arrays类,用于数组操作public class Main {// 主方法,程序的入口点public static void main(String[] args) {// 初始化一个整型数组,包含一些元素int arr[] = {1, 33, 2, 645, 747, 876, -1, -12345, 9, 10};// 调用sort1方法对数组进行排序sort1(arr);// 使用Arrays.toString方法打印排序后的数组System.out.println(Arrays.toString(arr));}// 定义一个私有静态方法sort1,用于对整型数组进行排序private static void sort1(int[] arr) {// 外层循环,控制间隔gap的值for(int gap = arr.length / 2 ; gap > 0; gap /= 2){// 内层循环,从gap开始遍历数组for(int i = gap; i < arr.length; i++){// 最内层循环,用于比较和交换元素for(int j = i - gap; j >= 0; j--){// 如果当前元素比它后面gap位置的元素大,则交换它们if(arr[j] > arr[j + gap]){int temp = arr[j];arr[j] = arr[j + gap];arr[j + gap] = temp;}}}}}
}

三  希尔排序的特性总结

希尔排序是对直接插入排序的优化。
当gap > 1时都是预排序,目的是让数组更接近于有序。当gap == 1时,数组已经接近有序的了,这样就会很快。这样整体而言,可以达到优化的效果。
希尔排序的时间复杂度不好计算,因为gap的取值方法很多,导致很难去计算,这里不深究。
时间复杂度O(N^1.5)
空间复杂度O(1)
稳定性:不稳定。

http://www.lryc.cn/news/473656.html

相关文章:

  • Junit + Mockito保姆级集成测试实践
  • 软件项目管理要点
  • ESP8266 连接 MQTT 服务器EMQX 连接MQTTX
  • Python中如何处理异常情况?
  • openpnp - 在openpnp中单独测试相机
  • Spark窗口函数
  • Idea、VS Code 如何安装Fitten Code插件使用
  • elasticsearch7.x在k8s中的部署
  • 校园社团信息管理平台:Spring Boot技术实战指南
  • 【Linux】从内核角度理解 TCP 的 全连接队列(以及什么是 TCP 抓包)
  • 太速科技-712-6U VPX飞腾处理器刀片计算机
  • 深度学习(八) TensorFlow、PyTorch、Keras框架大比拼(8/10)
  • thinkphp中命令行工具think使用,可用于快速生成控制器,模型,中间件等
  • Discourse 是否支持手机注册
  • 软件测试学习笔记丨Flask框架-请求与响应
  • 【C++笔记】list结构剖析及其模拟实现
  • C#进阶1
  • PHP如何对输出进行转义
  • Windows 10 安装Docker踩过的坑和解决-31/10/2024
  • 【应急响应】Linux植入恶意程序排查流程
  • 微信小程序app.js里面onLaunch里面的函数比page里面的onshow里面的方法后执行
  • 斐波那契时间序列,精准捕捉市场拐点 MT4免费公式源码!
  • 计算机的错误计算(一百四十)
  • JavaEE初阶---网络原理(四)--IP协议/DNS协议
  • LeetCode20:有效的括号
  • 简单介绍Class文件、Dex文件以及ELF文件
  • Vivo开奖了,劝退价。。
  • 鸿蒙打包hvigorw clean报错No npmrc file is matched in the current user folder解决
  • 无人机救援系统基本组成
  • git入门教程