程序员必须掌握的排序算法:希尔排序的原理与实现

简介: 程序员必须掌握的排序算法:希尔排序的原理与实现

📋 前言

希尔排序,不知道大家有没有感觉听起来都很吊吊的样子。事实也确实如此,希尔排序的性能在八大排序中某些特定情况是最强的,也是我们必学的高效算法之一。

一、什么是希尔排序

希尔排序,也称为缩小增量排序,是插入排序的一种高效改进版本也可以把它

  • 看做为插入排序的优化版

希尔排序法的基本思想是:先选定一个整数,把待排序文件中所有记录分成个组,所有距离为的记录分在同一组内,并对每一组内的记录进行排序。然后,取,重复上述分组和排序的工作。当到达=1时,所有记录在统一组内排好序

二、希尔排序的思想与实现

既然希尔排序是分组来实现的,那么这样做的好处呢?其实是因为每次分组跳着来进行选择排序,可以更快的吧大数调整到后面:

而插入排序却需要需要排 N*N 次才能找到最大值(最坏情况)

如上图当排的分组的区间为2的时候每次只需要排一次就可以达到全部有序了。

2.1 希尔排序的版本一

当我们看到分组的时候肯定大部分想的都是 定义一个 gap组然后再进行每次排序一直重复到 1 ;

  • 这里需要注意的是数据被分成了 gap组那么每次进行交换
  • 都需要间隔 gap 组

而被分成了 gap 组那么每次都需要排序gap次所以需要一个外循环

🍸 代码演示:

// 希尔排序
void ShellSort(int* a, int n)
{
  //方法一普通想法
  int gap = 3;
  for (int j = gap; j > 0; j--)
  {
    for (int i = j; i < n-j; i++)
    {
      int end = i;
      int tmp = a[end+j];
      while (end >= 0)
      {
        if (a[end] > tmp)
        {
          a[end + j] = a[end];
        }
        else
        {
          break;
        }
        end = end-j;
      }
      a[end + j] = tmp;
    }
  }
}

以上就是普通实现的希尔排序的代码了,而第二组排序的时候就是从第二个数据开始了:

  • 所以 i = j, 而每次需要跨越 gap 个数据

2.2 希尔排序的优化版本

但是上述代码有很大的局限性,希尔排序在排序每次 需要的 gap 分组都不一样:

  • 一般我们是采用 gap = n/2
  • 优化一下也可以写成 gap = n/3 +1

gap = n/3 +1 为什么要+1 呢因为当时候 2/3 的时候编译器回默认为 0 ,但我们这次还需要再排序一次数据所以需要+1;

🍸 代码演示:

void ShellSort(int* a, int n)
{
  int gap = n;
  while (gap > 1)
  {
    gap = gap / 3 + 1;
    for (int i = 0; i < n - gap; i++)
    {
      int end = i;
      int tmp = a[end + gap];
      while (end >= 0)
      {
        if (a[end] > tmp)
        {
          a[end + gap] = a[end];
          end -= gap;
        }
        else
        {
          break;
        }
      }
      a[end + gap] = tmp;
    }
  }
}

二、希尔排序的性能

希尔排序的特性总结:

  1. 希尔排序是对直接插入排序的优化。
  2. 当gap > 1时都是预排序,目的是让数组更接近于有序。当gap == 1时,数组已经接近有序的了,这样就会很快。这样整体而言,可以达到优化的效果。我们实现后可以进行性能测试的对比。
  3. 希尔排序的时间复杂度不好计算,因为gap的取值方法很多,导致很难去计算,因此在好些树中给出的希尔排序的时间复杂度都不固定:

《数据结构(C语言版)》— 严蔚敏

《数据结构-用面相对象方法与C++描述》— 殷人昆

因为咋们的gap是按照Knuth提出的方式取值的,而且Knuth进行了大量的试验统计,我们暂时就按照:O ( n 1.25 ) O(n^{1.25})O(n1.25)O ( 1.6 ∗ n 1.25 ) O(1.6*n^{1.25})O(1.6n1.25)来算。

  1. 稳定性:不稳定
目录
相关文章
机器学习/深度学习 算法 自动驾驶
129 0
|
25天前
|
机器学习/深度学习 算法 搜索推荐
从零开始构建图注意力网络:GAT算法原理与数值实现详解
本文详细解析了图注意力网络(GAT)的算法原理和实现过程。GAT通过引入注意力机制解决了图卷积网络(GCN)中所有邻居节点贡献相等的局限性,让模型能够自动学习不同邻居的重要性权重。
114 0
从零开始构建图注意力网络:GAT算法原理与数值实现详解
|
2月前
|
机器学习/深度学习 算法 文件存储
神经架构搜索NAS详解:三种核心算法原理与Python实战代码
神经架构搜索(NAS)正被广泛应用于大模型及语言/视觉模型设计,如LangVision-LoRA-NAS、Jet-Nemotron等。本文回顾NAS核心技术,解析其自动化设计原理,探讨强化学习、进化算法与梯度方法的应用与差异,揭示NAS在大模型时代的潜力与挑战。
294 6
神经架构搜索NAS详解:三种核心算法原理与Python实战代码
|
2月前
|
传感器 算法 定位技术
KF,EKF,IEKF 算法的基本原理并构建推导出四轮前驱自主移动机器人的运动学模型和观测模型(Matlab代码实现)
KF,EKF,IEKF 算法的基本原理并构建推导出四轮前驱自主移动机器人的运动学模型和观测模型(Matlab代码实现)
|
2月前
|
算法
离散粒子群算法(DPSO)的原理与MATLAB实现
离散粒子群算法(DPSO)的原理与MATLAB实现
89 0
|
3月前
|
机器学习/深度学习 人工智能 编解码
AI视觉新突破:多角度理解3D世界的算法原理全解析
多视角条件扩散算法通过多张图片输入生成高质量3D模型,克服了单图建模背面细节缺失的问题。该技术模拟人类多角度观察方式,结合跨视图注意力机制与一致性损失优化,大幅提升几何精度与纹理保真度,成为AI 3D生成的重要突破。
189 0
|
3月前
|
算法 区块链 数据安全/隐私保护
加密算法:深度解析Ed25519原理
在 Solana 开发过程中,我一直对 Ed25519 加密算法 如何生成公钥、签名以及验证签名的机制感到困惑。为了弄清这一点,我查阅了大量相关资料,终于对其流程有了更清晰的理解。在此记录实现过程,方便日后查阅。
175 0
|
4月前
|
消息中间件 存储 缓存
zk基础—1.一致性原理和算法
本文详细介绍了分布式系统的特点、理论及一致性算法。首先分析了分布式系统的五大特点:分布性、对等性、并发性、缺乏全局时钟和故障随时发生。接着探讨了分布式系统理论,包括CAP理论(一致性、可用性、分区容错性)和BASE理论(基本可用、软状态、最终一致性)。文中还深入讲解了两阶段提交(2PC)与三阶段提交(3PC)协议,以及Paxos算法的推导过程和核心思想,强调了其在ZooKeeper中的应用。最后简述了ZAB算法,指出其通过改编的两阶段提交协议确保节点间数据一致性,并在Leader故障时快速恢复服务。这些内容为理解分布式系统的设计与实现提供了全面的基础。
|
4月前
|
存储 算法 安全
Java中的对称加密算法的原理与实现
本文详细解析了Java中三种常用对称加密算法(AES、DES、3DES)的实现原理及应用。对称加密使用相同密钥进行加解密,适合数据安全传输与存储。AES作为现代标准,支持128/192/256位密钥,安全性高;DES采用56位密钥,现已不够安全;3DES通过三重加密增强安全性,但性能较低。文章提供了各算法的具体Java代码示例,便于快速上手实现加密解密操作,帮助用户根据需求选择合适的加密方案保护数据安全。
345 58

热门文章

最新文章