排序算法之希尔排序


title: 希尔排序
date: 2024-7-25 10:48:15 +0800
categories:

  • 排序算法
    tags:
  • 排序
  • 算法
  • 希尔排序
    description: 1959年Shell发明,是简单插入排序的改进版。是一种高效的排序算法,通过分组和逐步缩减增量,使得数组在接近有序的情况下进行最终排序,从而提高效率。
    math: true

希尔排序

希尔排序(Shell Sort)是一种基于插入排序的排序算法,通过优化插入排序中的比较和移动操作,实现更高效的排序。希尔排序通过将数组分成若干子序列分别进行插入排序,使得数据项的步长逐渐减少,最终进行一次普通的插入排序。本文将详细介绍希尔排序的原理、步骤、示例、复杂度分析及其Java代码实现。

希尔排序的原理

  1. 分组:将待排序数组按某个增量分组,对每组分别进行插入排序。
  2. 缩减增量:逐步缩减增量,重复上述分组和排序过程。
  3. 最终排序:当增量缩减为1时,对整个数组进行一次普通的插入排序。

希尔排序通过多次分组和排序,使得数组在接近有序的情况下进行最终排序,从而提高效率。

希尔排序的步骤

  1. 选择初始增量:选择一个较大的初始增量(一般为数组长度的一半)。
  2. 分组并插入排序:按当前增量将数组分组,对每组分别进行插入排序。
  3. 缩减增量:将增量减半,重复分组和排序过程。
  4. 最终排序:当增量缩减为1时,对整个数组进行一次插入排序。

图示

希尔排序

示例

希尔排序示例

步长

  1. Shell 的原始序列: N 2 \frac{N}{2} 2N, N 4 \frac{N}{4} 4N , …, 1 (重复除以 2);

  2. Hibbard 增量: 1, 3, 7, …, 2 k − 1 2^k-1 2k1 ;

  3. Knuth 增量: 1, 4, 13, …, ( 3 k − 1 ) 2 \frac{(3^k-1)}{2} 2(3k1) ;

  4. Sedgewick 增量: 1, 5, 19, 41, 109, …
    它是通过将两个序列的元素交织得到的:

    1, 19, 109, 505, 2161,……, 9 ( 4 k – 2 k ) + 1 9(4^k–2^k)+1 9(4k2k)+1, k = 0, 1, 2, 3,…
    5, 41, 209, 929, 3905,…… 2 k + 2 ( 2 k + 2 – 3 ) + 1 2^{k+2}(2^{k+2}–3)+1 2k+2(2k+2–3)+1, k = 0, 1, 2, 3, …

复杂度分析

步长的选择是希尔排序的重要部分。只要最终步长为1任何步长序列都可以工作。算法最开始以一定的步长进行排序。然后会继续以一定步长进行排序,最终算法以步长为1进行排序。当步长为1时,算法变为普通插入排序,这就保证了数据一定会被排序。

Donald Shell最初建议步长选择为 n 2 \frac {n}{2} 2n并且对步长取半直到步长达到1。虽然这样取可以比 O ( n 2 ) O(n^{2}) O(n2)类的算法(插入排序)更好,但这样仍然有减少平均时间和最差时间的余地。

步长序列最坏情况下复杂度
n 2 i \frac {n}{2^{i}} 2in O ( n 2 ) O(n^{2}) O(n2)
2 k − 1 2^{k}-1 2k1 O ( n 3 2 ) O(n^{\frac {3}{2}}) O(n23)
2 i 3 j 2^{i}3^{j} 2i3j O ( n log ⁡ 2 n ) O(n\log ^{2}n) O(nlog2n)

已知的最好步长序列是由Sedgewick提出的(1, 5, 19, 41, 109,…)。“比较在希尔排序中是最主要的操作,而不是交换。”用这样步长序列的希尔排序比插入排序要快,甚至在小数组中比快速排序和堆排序还快,但是在涉及大量数据时希尔排序还是比快速排序慢。

另一个在大数组中表现优异的步长序列是斐波那契数列除去0和1将剩余的数以黄金分割比的两倍的幂进行运算得到的数列:(1, 9, 34, 182, 836, 4025, 19001, 90358, 428481, 2034035, 9651787, 45806244, 217378076, 1031612713,…)

时间复杂度

  • 最佳情况 O ( n log ⁡ 2 n ) O(n \log^2 n) O(nlog2n)
  • 最坏情况 O ( n 2 ) O(n^2) O(n2)
  • 平均情况 O ( n 1.3 ) O(n^{1.3}) O(n1.3)

空间复杂度

  • 空间复杂度 O ( 1 ) O(1) O(1)

希尔排序的代码实现(Java)

public class ShellSort {// 主排序函数public static void shellSort(int[] arr) {int n = arr.length;// 选择初始增量for (int gap = n / 2; gap > 0; gap /= 2) {// 按增量进行插入排序for (int i = gap; i < n; i++) {int temp = arr[i];int j;// 插入排序for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {arr[j] = arr[j - gap];}arr[j] = temp;}}}// 主函数public static void main(String[] args) {int[] arr = {38, 27, 43, 3, 9, 82, 10};System.out.println("Given Array:");for (int num : arr) {System.out.print(num + " ");}System.out.println();// 调用希尔排序函数shellSort(arr);System.out.println("\nSorted Array:");for (int num : arr) {System.out.print(num + " ");}System.out.println();}
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/401969.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【docker】dockerfile部署lnmp、docker compose初步

1、dockerfile部署lnmp mkdir /opt/lnmp cd /opt/lnmp mkdir nginx mysql php docker network create --subnet20.0.0.0/24 lnmp-net将wordpress文件夹拷贝到nginx、php文件夹 /opt/nginx/Dockerfile: # 使用官方的nginx镜像作为基础镜像 FROM nginx:latest# 复制默认配置文件…

分销商城小程序系统渠道拓展

线上卖货渠道很多&#xff0c;想要不断提高营收和新客获取&#xff0c;除了自己和工具本身努力外&#xff0c;还需要其他人的帮助来提高商城店铺的整体销量。 搭建saas商城系统网站/小程序&#xff0c;后台上货&#xff0c;设置支付、配送、营销、精美模板商城装修等内容&…

快速解析数据挖掘,最短时间明白什么是数据挖掘------下

信息损失函数 &#xff08;Information Loss Function&#xff09;是衡量在数据转换或处理过程中信息丢失的程度的函数。在数据科学、机器学习和统计学中&#xff0c;信息损失是一个重要的概念&#xff0c;尤其是在数据降维、特征选择、数据压缩和隐私保护等领域。 信息损失函…

数字化营销在公域场景中的无限可能

在如今的商业领域&#xff0c;公域场景为企业提供了广阔的发展空间&#xff0c;而数字化营销则成为了企业在这些场景中脱颖而出的关键利器。 ​ 一、电商平台营销 当企业在淘宝、京东等大型电商平台开设店铺&#xff0c;数字化营销便开始大显身手。 企业不仅能踊跃参与像双十…

【MySQL】explain 执行计划各字段解析

MySQL 如何读写数据&#xff1f;https://blog.csdn.net/weixin_43551213/article/details/140862538 MySQL 索引https://blog.csdn.net/weixin_43551213/article/details/140847916 在上一篇文章中提到了索引&#xff0c;而添加索引是优化 SQL 语句的一个方式&#xff0c;但是…

计算机网络——运输层(进程之间的通信、运输层端口,UDP与TCP、TCP详解)

运输层协议概述 进程之间的通信 运输层向它上面的应用层提供通信服务。 当网络边缘部分的两台主机使用网络核心部分的功能进行端到端的通信时&#xff0c;都要使用协议栈中的运输层&#xff1b;而网络核心部分中的路由器在转发分组时只用到下三层的功能。 Q1&#xff1a;我们…

mysql windows安装与远程连接配置

安装包在主页资源中 一、安装(此安装教程为“mysql-installer-community-5.7.41.0.msi”安装教程&#xff0c;安装到win10环境) 保持默认选项&#xff0c;点击”Next“。 点开第一行加号展开一路展开找到“MySQL Server 5,7,41 - X64”点击选中点击一下中间只想右侧的箭头看到…

Attention注意力机制

神经网络注意力机制代码实现 import torch import torch.nn as nn import torch.nn.functional as F# MyAtt类实现思路分析 # 1 init函数 (self, query_size, key_size, value_size1, value_size2, output_size) # 准备2个线性层 注意力权重分布self.attn 注意力结果表示按照指…

简单测试AOP五种增强执行时机

1. 目标方法类&#xff0c;spring代理bean Component public class Test {public void test(){System.out.println("test 目标方法");}public void testException(){throw new RuntimeException();} } 2. 配置类 Configuration ComponentScan EnableAspectJAutoPr…

unity项目打包为webgl后应用于vue项目中(iframe模式)的数据交互

参考文章&#xff1a; 1.Unity打包WebGL: 导入Vue 2.unity文档-WebGL&#xff1a;与浏览器脚本交互 3.unity与vue交互(无第三方插件&#xff09; 目录 一、前期工作1.新建.jslib文件2.新建.cs脚本3. 新建一个Text对象和button按钮对象4.添加脚本空对象UIEvent5.导出unity为w…

Windows配置开机直达桌面并跳过锁屏登录界面在 Windows 10 中添加在启动时自动运行的应用

目录 Win10开机直达桌面并跳过锁屏登录界面修改组策略修改注册表跳过登录界面 在 Windows 10 中添加在启动时自动运行的应用设置系统级别服务一、Windows下使用sc将应用程序设置为系统服务1. 什么是sc命令&#xff1f;2. sc命令的基本语法3. 创建Windows服务的步骤与示例创建服…

CANoe软件中Trace窗口的筛选栏标题不显示(空白)的解决方法

文章目录 问题描述原因分析解决方案扩展知识总结问题描述 不知道什么情况,CANoe软件中Trace窗口的筛选栏标题突然不显示了,一片空白。现象如下: 虽然不影响CANoe软件的使用,但是观感上非常难受,对于强迫症患者非常不友好。 原因分析 按照常规思路,尝试了: 1、重启CAN…

K8S中使用英伟达GPU —— 筑梦之路

前提条件 根据不同的操作系统&#xff0c;安装好显卡驱动&#xff0c;并能正常识别出来显卡&#xff0c;比如如下截图&#xff1a; GPU容器创建流程 containerd --> containerd-shim--> nvidia-container-runtime --> nvidia-container-runtime-hook --> libnvid…

MoExtend: 模态和任务扩展调整的新专家

MoExtend: Tuning New Experts for Modality and Task Extension GitHub - zhongshsh/MoExtend: ACL 2024 (SRW) https://arxiv.org/pdf/2408.03511 大型语言模型&#xff08;LLM&#xff09;在各种任务中表现出色&#xff0c;然而其应用范围受限于主要在文本数据上进行训练。…

【vSphere 7/8】深入浅出 vSphere 证书 Ⅰ—— 初识和了解 vSphere证书

目录 引子1. vCenter Server 证书服务1.1 vSphere 安全证书&#xff08;1&#xff09;vSphere 安全证书的类型和有效期 1.2在 vSphere Client 中初识 vSphere 证书&#xff08;1&#xff09;vCenter 8.0.3 的 vSphere Client 界面&#xff08;2&#xff09;vCenter Server 7.0 …

TCP/UDP实现网络通信

TCP实现网络通信 1.服务端 #include<myhead.h>//1服务端定义:端口号\id号 #define SER_PIPR 6666 #define SER_IP "196.168.111.186" //通过ifconfig查看ip int main(int argc, const char *argv[]) {//1创建套接字int sfd socket(AF_INET,SOCK_STREAM,0);…

深度解析Edge SCDN与CDN:安全加速,全面防护

在现代互联网应用中&#xff0c;CDN已成为提高网站和应用性能不可或缺的技术之一。然而&#xff0c;随着网络安全威胁的日益严峻&#xff0c;单纯依靠CDN提供的加速服务已经不足以满足企业的安全需求。因此&#xff0c;Edge SCDN出现了&#xff0c;它不仅具备CDN的加速特性&…

解锁客户增长新密码:“老带新”策略的深度剖析与实战指南

客户推荐是什么&#xff0c;为何那么重要&#xff1f; 客户推荐是指满意的客户自愿地将其认为优质的产品或服务推荐给他们的社交网络成员&#xff0c;如朋友、家人或同事&#xff0c;这种推荐行为可以是自发的口碑传播&#xff0c;也可以是通过产品方推出的“老带新”奖励计划来…

OpenCV图像滤波(12)图像金字塔处理函数pyrDown()的使用

操作系统&#xff1a;ubuntu22.04 OpenCV版本&#xff1a;OpenCV4.9 IDE:Visual Studio Code 编程语言&#xff1a;C11 算法描述 函数主要是对图像进行模糊处理并将其降采样。 默认情况下&#xff0c;输出图像的大小计算为 Size((src.cols1)/2, (src.rows1)/2)&#xff0c;但…

汽车维修预约服务系统的设计与实现

TOC springboot317汽车维修预约服务系统的设计与实现 第1章 绪论 1.1选题动因 当前的网络技术&#xff0c;软件技术等都具备成熟的理论基础&#xff0c;市场上也出现各种技术开发的软件&#xff0c;这些软件都被用于各个领域&#xff0c;包括生活和工作的领域。随着电脑和笔…