【基础算法】希尔排序法 & C++实现 | [实例过程详细分析]

简介: 希尔排序算法是基于插入排序法的思想,其又被称为希尔排序或者缩小增量排序。它的具体流程如下:(结合希尔排序算法代码段理解)

●希尔排序法


1.简要介绍

       希尔排序算法是基于插入排序法的思想,其又被称为希尔排序或者缩小增量排序。它的具体流程如下:(结合希尔排序算法代码段理解)

for (int r = n / 2; r >= 1; r /= 2)  //化组排序
  {
  for (int i = r; i < n; i++)
  {
    int temp = arr[i];
    int j = i - r;
    while (j >= 0 && temp < arr[j])
    {
    arr[j + r] = arr[j];
    j -= r;
    }
    arr[j + r] = temp;
  }
  }

       ①将有n个元素的数组分成n/2个数字序列(化组操作)。进行第一次循环:第1个数据和第n/2+1个数字序列为一个比较对,判断是否执行while循环,若执行则进行循环操作(插入排序思想);反之,则将n/2+1数字放回原位。进行第二次循环:第2个数据和第n/2+2个数字序列为一个比较对,判断是否执行while循环,若执行则进行循环操作(插入排序思想);反之,则将n/2+2数字放回原位。操作如上......(插入排序法:http://t.csdn.cn/ukSxu


       ②一整次循环使每一个序列对排好顺序


       ③然后,再将这有n个元素的数组分成n/4个序列(化组操作),再次进行排序


       ④不断重复上述流程,随着序列减少,直到变为一个序列对,也就完成了整个排序过程


2.图形化演示

(在下面的图中,虚线表示不符合while循环判断,实线表示符合并执行while循环判断,实线下面的数字符号为执行了几次的while循环。红色箭头的temp在每次的while判断语句中为每一个数字序列比较对中的值,它在每次循环中是进行后移的。结合代码和输出结果对下面的过程进行理解)


初始状态:

51972d3c269464de7992faed226e7dba_d89b0210bdd14c12b7a59aaec63dfbab.png第一次化组:

3c006511a2b1383795112c75009d7346_05b3edceac254f8d901b560c48f3d646.png


第二次化组:

e144f24de3ee469320339a3067f5acef_365900fa185244e4952a633216a1b409.png

第三次化组:

98b46b36913adf9389d48afde961481b_ee36c302034747aaaa576afdba39432b.png

结束状态:

7d8e75532653abace3e961865b581f09_0a98353ff37d4516b0c1d8db56861b4a.png

3.代码如下

#include<iostream>
using namespace std;
#define size 10
class shellsort {
public:
  void shellsort_1();
  void showresult();
  int arr[size];
};
void shellsort::shellsort_1()
{   
  int x=0;
  for (int r = size / 2; r >= 1; r /= 2)  //化组排序
  {
  for (int i = r; i < size; i++)
  {
    int temp = arr[i];
    int j = i - r;
    while (j >= 0 && temp < arr[j])
    {
    arr[j + r] = arr[j];
    j -= r;
    }
    arr[j + r] = temp;
  }
  //测试代码
  x++;
  cout << "第" << x << "步排序的结果:";
  for (int i = 0; i < size; i++)
  {
    cout << arr[i] << " ";
  }
  cout << endl;
  }
}
void shellsort::showresult()
{
  for (int i = 0; i < size; i++)
  {
  cout << arr[i] << " ";
  }
  cout << endl;
}
void text()
{
  shellsort ss;
  cout << "请输入要排序的10个数:" << endl;
  for (int i = 0; i < size; i++)
  {
  cin >> ss.arr[i];
  }
  ss.shellsort_1();
  cout << "排序后的10个数为:" << endl;
  ss.showresult();
}
int main()
{
  text();
}

4.结果如下

60d7ec8d37a8904f100beb3af0b0c6a1_d3ce486acc184f5c91ff81d4986e5115.png



目录
相关文章
|
24天前
|
运维 监控 JavaScript
基于 Node.js 图结构的局域网设备拓扑分析算法在局域网内监控软件中的应用研究
本文探讨图结构在局域网监控系统中的应用,通过Node.js实现设备拓扑建模、路径分析与故障定位,提升网络可视化、可追溯性与运维效率,结合模拟实验验证其高效性与准确性。
152 3
|
4月前
|
机器学习/深度学习 边缘计算 算法
NOMA和OFDMA优化算法分析
NOMA和OFDMA优化算法分析
255 127
|
5月前
|
存储 监控 算法
基于 C++ 哈希表算法实现局域网监控电脑屏幕的数据加速机制研究
企业网络安全与办公管理需求日益复杂的学术语境下,局域网监控电脑屏幕作为保障信息安全、规范员工操作的重要手段,已然成为网络安全领域的关键研究对象。其作用类似网络空间中的 “电子眼”,实时捕获每台电脑屏幕上的操作动态。然而,面对海量监控数据,实现高效数据存储与快速检索,已成为提升监控系统性能的核心挑战。本文聚焦于 C++ 语言中的哈希表算法,深入探究其如何成为局域网监控电脑屏幕数据处理的 “加速引擎”,并通过详尽的代码示例,展现其强大功能与应用价值。
130 2
|
6月前
|
数据采集 机器学习/深度学习 算法
别急着上算法,咱先把数据整明白:大数据分析的5个基本步骤,你都搞对了吗?
别急着上算法,咱先把数据整明白:大数据分析的5个基本步骤,你都搞对了吗?
329 4
|
22天前
|
存储 边缘计算 算法
【太阳能学报EI复现】基于粒子群优化算法的风-水电联合优化运行分析(Matlab代码实现)
【太阳能学报EI复现】基于粒子群优化算法的风-水电联合优化运行分析(Matlab代码实现)
|
2月前
|
机器学习/深度学习 算法 5G
【MUSIC、最大似然与克拉美-罗下界】MUSIC与ESPRIT 算法来估计到达角(AoA),并尝试推导克拉美-罗下界(CRLB)以分析其性能研究(Matlab代码实现)
【MUSIC、最大似然与克拉美-罗下界】MUSIC与ESPRIT 算法来估计到达角(AoA),并尝试推导克拉美-罗下界(CRLB)以分析其性能研究(Matlab代码实现)
108 0
|
3月前
|
编解码 算法 5G
MIMO雷达空间谱估计中Capon算法与MUSIC算法的对比分析及实现
MIMO雷达空间谱估计中Capon算法与MUSIC算法的对比分析及实现
230 2
|
3月前
|
人工智能 自然语言处理 算法
2025 年 7 月境内深度合成服务算法备案情况分析报告
2025年7月,中央网信办发布第十二批深度合成算法备案信息,全国389款产品通过备案,服务提供者占比超七成。截至7月14日,全国累计备案达3834款,覆盖文本、图像、音视频等多模态场景,广泛应用于生活服务、医疗、金融等领域。广东以135款居首,数字人、AI客服等C端应用主导,民营企业成主力,国企聚焦公共服务。随着AI政策推动,备案已成为AI产品合规上线关键环节。
|
3月前
|
存储 监控 算法
基于跳表数据结构的企业局域网监控异常连接实时检测 C++ 算法研究
跳表(Skip List)是一种基于概率的数据结构,适用于企业局域网监控中海量连接记录的高效处理。其通过多层索引机制实现快速查找、插入和删除操作,时间复杂度为 $O(\log n)$,优于链表和平衡树。跳表在异常连接识别、黑名单管理和历史记录溯源等场景中表现出色,具备实现简单、支持范围查询等优势,是企业网络监控中动态数据管理的理想选择。
105 0
|
5月前
|
监控 算法 数据处理
基于 C++ 的 KD 树算法在监控局域网屏幕中的理论剖析与工程实践研究
本文探讨了KD树在局域网屏幕监控中的应用,通过C++实现其构建与查询功能,显著提升多维数据处理效率。KD树作为一种二叉空间划分结构,适用于屏幕图像特征匹配、异常画面检测及数据压缩传输优化等场景。相比传统方法,基于KD树的方案检索效率提升2-3个数量级,但高维数据退化和动态更新等问题仍需进一步研究。未来可通过融合其他数据结构、引入深度学习及开发增量式更新算法等方式优化性能。
160 17