「数组」希尔排序 / 区间增量优化(C++)

目录

概述

思路

核心概念:增量d

算法过程

流程

Code

优化方案

区间增量优化

Code(pro)

复杂度


概述

我们在「数组」冒泡排序|选择排序|插入排序 / 及优化方案(C++)中讲解了插入排序。

它有这么两个特点:

①待排序元素较少时效率高。

②待排序元素较有序时效率高。

正如同快速排序时冒泡排序的究极promax进化版,希尔排序则是充分利用了这两个特点的插入排序promax进化版。


思路

战略是这样的:多次进行小数目的插入排序使得数组变得相对有序。

我们要采取一点策略:

通过多轮小型插入排序使得数组逐渐有序,然后就可以将小型插入排序变成中型插入排序。通过多轮中型插入排序使得数组几乎有序,然后就可以将小型插入排序变成整体插入排序。

通过一轮整体插入排序使得数组完全有序。

这个“小型的插入排序”的目的是使得数组逐渐有序,这意味这我们要在整个数组中挑选几个数出来,对他们进行插入排序。

这种挑选是很有讲究的:

我们挑选的数必须能均等地位于整个数组的不同位置中,这样才能使整个数组愈发有序。

我们挑选的数必须能覆盖整个数组,这样才能使整个数组整体愈发有序。

于是就有了增量的概念。


核心概念:增量d

增量d的本质就是对整个数组进行间隔分组:

我们将arr[i],arr[i+d],arr[i+2d]...分为一组,在组内进行插入排序。

完成一组后再完成下一组,直到所有组都进行了组内插入排序。之后减小增量d重新分组,重复上述过程,直到d=1,进行完整的插入排序。

通常我们初始化d=len/2,然后依次d/=2。(向下取整)

例如:

 len=11;arr[i] 7 1 8 9 5 6 4 2 3 10 0↓d=len/2;
┌--------------------------------------------┐d=5;i  0 1 2 3 4 5 6 7 8 9 10arr[i] 7 1 8 9 5 6 4 2 3 10 0↓d↓group0 7----d----6          0group1   1----d----4group2     8----d----2group3       9----d----3group4         5----d----10↓insertion_sort()↓group0 0         6          7group1   1         4group2     2         8group3       3         9group4         5         10↓after sorted↓arr[i] 0 1 2 3 5 6 4 8 9 10 7
└--------------------------------------------┘↓d/=2;
┌--------------------------------------------┐d=2;i  0 1 2 3 4 5 6 7 8 9 10arr[i] 0 1 2 3 5 6 4 8 9 10 7↓d↓group0 0-d-2   5   4   9    7group1   1-d-3   6   8   10↓insertion_sort()↓group0 0   2   4   5   7    9group1   1   3   6   8   10↓after sorted↓arr[i] 0 1 2 3 4 6 5 8 7 10 9
└--------------------------------------------┘↓d/=2;
┌--------------------------------------------┐d=1;i  0 1 2 3 4 5 6 7 8 9 10arr[i] 0 1 2 3 4 6 5 8 7 10 9↓insertion_sort()↓arr[i] 0 1 2 3 4 5 6 7 8 9 10
└--------------------------------------------┘

我们注意到,d的值和分组数量是相等的

因为arr[i]与arr[i+d]为同组,而arr[i+d]与arr[i]间共有d-1组各不相同,再加上arr[i]这一组,共d组。

这一点将会在分组代码实现时利用到。 

*注意*:分组图只是我们的具象化表达,希尔排序是原地算法,不会使用额外的空间储存每一组。 


算法过程

流程

共有四层循环:

①最外层循环(增量减半缩小层)while (d/=2)控制增量减半

②次外层循环(按照增量分组层)for (int group = 0; group < d; group++)进行分组

③次内层循环for (int i = group+d; i < len; i += d)进行组内插入排序(根据插入排序的原理,首个元素可以跳过)

④最内层循环for ( j= i-d; j >= 0; j -= d)将组内的元素插入到组内的有序区中。

你会发现内部的两层循环就是普通插入排序的是实现,只不过普通插入排序的增量d始终为1。

Code

void shell_sort(int arr[], int len) {int d = len;while (d /= 2) {for (int group = 0; group < d; group++) {for (int i = group+d; i < len; i += d) {int temp = arr[i], j = i - d;for (; j >= 0; j -= d) {if (temp < arr[j])arr[j + d] = arr[j];else break;}arr[j + d] = temp;}}}
}

优化方案

区间增量优化

Knuth大神提出了另一种增量策略:d=d/3+1。(+1是为了使得d==2时下次取到d==1)

你会意识到上一种分组的增量减半缩小层是log₂N级别的,而这种则是log₃N级别的

但是这种优化不一定是最理想的,其实与上一种分组各有胜负:

因为这只是优化了增量减半缩小层,而每层内部进行了更多的比较。

Code(pro)

void SLsort(int arr[], int len) {int d = len;while (d = d/3+1) {for (int group = 0; group < d; group++) {for (int i = group + d; i < len; i += d) {int temp = arr[i], j = i - d;for (; j >= 0; j -= d) {if (temp < arr[j])arr[j + d] = arr[j];else break;}arr[j + d] = temp;}}if (d == 1)break;}
}

*注意*: 需要加入d==1的判断语句来结束最外层循环。


复杂度

时间复杂度:O(n¹·³)(或:O(nlog²n)

空间复杂度:O(1)

事实上,希尔排序的时间复杂度不是nlogn,它的证明极其困难,略去不表。

百万数量级抗压测试

int main()
{   int nums = 5000000;int* arr1 = new int[nums];int* arr2 = new int[nums];for (int i = 0; i < nums; i++) {int x = mt()%1000;arr1[i] =arr2[i]= x;}DWORD tick1 = GetTickCount64();shell_sort(arr1, nums);//show(arr, nums);DWORD tick2 = GetTickCount64();cout <<"Shell's strategy(ms):" << tick2 - tick1 << endl;DWORD tick3 = GetTickCount64();SLsort(arr2, nums);//show(arr, nums);DWORD tick4 = GetTickCount64();cout <<"Knuth's strategy(ms):" << tick4 - tick3 << endl;delete[] arr1;delete[] arr2;return 0;
}

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

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

相关文章

[Qt][Qt 文件]详细讲解

目录 1.输入输出设备类2.文件读写类3.文件和目录信息类 1.输入输出设备类 在Qt中&#xff0c;⽂件读写的类为QFile&#xff0c;其⽗类为QFileDevice QFileDevice提供了⽂件交互操作的底层功能QFileDevice的⽗类是QIODevice&#xff0c;其⽗类为QObject QIODevice是Qt中所有I/O…

【企业高性能web服务器】

目录 一、Nginx 介绍1、 Nginx 功能介绍2、基础特性3、Nginx 模块介绍 二、Nginx 编译安装1、编写systemd服务 三、平滑升级和回滚1、平滑升级的流程2、升级2、回滚 四、 Nginx 核心配置详解1、实现 nginx 的高并发配置2、Nginx 账户认证功能3、nginx作为下载服务器配置 五、re…

QT-监测文件内容重复工具)

QT-监测文件内容重复工具 一、演示效果二、核心代码三、下载链接 一、演示效果 二、核心代码 #include "widget.h" #include "ui_widget.h" #include <QDir> #include <QFile> #include <QCryptographicHash> #include <QApplicatio…

如何用Python构建高校爬虫与k-means算法实现专业评分可视化分析

&#x1f34a;作者&#xff1a;计算机毕设匠心工作室 &#x1f34a;简介&#xff1a;毕业后就一直专业从事计算机软件程序开发&#xff0c;至今也有8年工作经验。擅长Java、Python、微信小程序、安卓、大数据、PHP、.NET|C#、Golang等。 擅长&#xff1a;按照需求定制化开发项目…

多线程、多进程,还是异步?-- Python 并发 API 如何选择

如何选择正确的 Python 并发 API模块 &#xff1f; Python 标准库提供了三种并发 API &#xff0c; 如何知道你的项目应该使用哪个 API&#xff1f; 在本教程将带逐步了解各API的特性、区别以及各自应用场景&#xff0c;指导你选择最合适的并发 API。 多线程、多进程&#xff0…

F1 F4 Fn lock 指示灯不亮 联想笔记本 thinkpad

问题描述&#xff1a;F1 F4 Fn lock 指示灯开机的时候亮&#xff0c;但是使用的时候虽然能够发挥正常功能&#xff0c;但是指示灯一直熄灭&#xff0c;指示灯不亮。 电脑型号&#xff1a;联想笔记本 thinkpad E14 Gen 2 。本方案应该适用于所有联想电脑。 解决方法&#xff1a;…

鸿蒙内核源码分析(静态链接篇) | 完整小项目看透静态链接过程

下图是一个可执行文件编译&#xff0c;链接的过程. 本篇将通过一个完整的小工程来阐述ELF编译&#xff0c;链接过程&#xff0c;并分析.o和bin文件中各区&#xff0c;符号表之间的关系.从一个崭新的视角去看中间过程. 准备工作 先得有个小工程&#xff0c;麻雀虽小&#xff0…

基于数据复杂度的数据库选型

数据模型的选择对于 IT 系统的开发至关重要&#xff0c;它不仅决定了数据存储和处理的方式&#xff0c;影响系统的性能、扩展性以及维护性等。本质上来说&#xff0c;不同的数据模型反映了我们对业务问题的不同思考和抽象程度。 今天我们从不同数据模型对于复杂数据和关系的支…

【Qt】常用控件QCalendarWidget的使用

常用控件QCalendarWidget的使用 QCalendarWidget表示一个日历 核心属性 属性说明 selectDate 当前选中的⽇期 minimumDate 最⼩⽇期 maximumDate 最⼤⽇期 firstDayOfWeek 每周的第⼀天(也就是⽇历的第⼀列) 是周⼏. gridVisible 是否显⽰表格的边框 selectionMode…

python3爬虫(未完结)

一个简单的例子&#xff1a;爬取自己的csdn博客&#xff0c;统计每篇博客的访问量&#xff0c;制作一个柱状图&#xff0c;以访问量从大到小的方式显示。 1. 首先从“个人主页”爬取所有所有文章的链接 1.1 打开个人主页&#xff0c;右键->检查&#xff1a;可以看到每篇文章…

类和对象(下)(2)

类和对象&#xff08;下&#xff09;(2) static成员 • ⽤static修饰的成员变量&#xff0c;称之为静态成员变量&#xff0c;静态成员变量⼀定要在类外进⾏初始化。 • 静态成员变量为当前类的所有对象所共享&#xff0c;不属于某个具体的对象&#xff0c;不存在对象中&#…

HiveSQL实战——大厂面试真题

一、字节跳动 最高峰同时直播人数 https://blog.csdn.net/SHWAITME/article/details/135918264 0 问题描述 有如下数据记录直播平台主播上播及下播时间&#xff0c;根据该数据计算出平台最高峰同时直播人数。 ------------------------------------------------------ | us…

CTFHUB | web进阶 | JSON Web Token | 无签名

一些JWT库也支持none算法&#xff0c;即不使用签名算法。当alg字段为空时&#xff0c;后端将不执行签名验证 开启题目 账号密码随便输&#xff0c;登录之后显示只有 admin 可以获得 flag 在此页面抓包发到 repeater&#xff0c;这里我们需要用到一个 Burp 插件&#xff0c;按图…

Linux信号机制探析--信号的产生

&#x1f351;个人主页&#xff1a;Jupiter. &#x1f680; 所属专栏&#xff1a;Linux从入门到进阶 欢迎大家点赞收藏评论&#x1f60a; 目录 &#x1f4da;信号什么是信号&#xff1f;为什么要有信号&#xff1f;查看Linux系统中信号 &#x1f388;信号产生&#x1f4d5;kill…

【流媒体】RTMPDump—RTMP_ConnectStream(创建流连接)

目录 1. RTMP_ConnectStream函数1.1 读取packet&#xff08;RTMP_ReadPacket&#xff09;1.2 解析packet&#xff08;RTMP_ClientPacket&#xff09;1.2.1 设置Chunk Size&#xff08;HandleChangeChunkSize&#xff09;1.2.2 用户控制信息&#xff08;HandleCtrl&#xff09;1…

JAVA面试汇总

JAVA面试 JAVA面试精华 面试精华 互联网面试真题

keepalived详解

概念 keepalived 是一款基于 VRRP&#xff08;Virtual Router Redundancy Protocol&#xff0c;虚拟路由冗余协议&#xff09;协议来实现高可用&#xff08;High Availability, HA&#xff09;的轻量级软件。它主要用于防止单点故障&#xff0c;特别是在 Linux 环境下&#xff…

使用maven快速生成打包文件

最近在部署基于SpringBoot开发的项目时&#xff0c;由于微服务较多&#xff0c;本地工程编译后只得出一个JAR包&#xff0c;部署起来实在不方便&#xff0c;因此总想着怎么偷偷懒&#xff0c;执行一次命令编译出整个部署的文件。先说结果&#xff0c;最后期望打包的目录如下&am…

C++ | 继承

前言 本篇博客讲解c中的继承 &#x1f493; 个人主页&#xff1a;普通young man-CSDN博客 ⏩ 文章专栏&#xff1a;C_普通young man的博客-CSDN博客 ⏩ 本人giee: 普通小青年 (pu-tong-young-man) - Gitee.com 若有问题 评论区见&#x1f4dd; &#x1f389;欢迎大家点赞&…

Kubernetes 如何给pod的 /etc/hosts文件里面添加条目

创建pod的时候&#xff0c;pod会在其/etc/hosts里面添加一个条目。 [rootmaster ~]# kubectl get pod -o wide NAME READY STATUS RESTARTS AGE IP NODE NOMINATED NODE READINESS GATES dns-test 1/1 R…