【算法基础】希尔排序解析

本文涉及的产品
云解析 DNS,旗舰版 1个月
全局流量管理 GTM,标准版 1个月
公共DNS(含HTTPDNS解析),每月1000万次HTTP解析
简介: 希尔排序的基本思想是先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序,待整个序列中的记录"基本有序"时,再对全体记录进行依次直接插入排序。
作者:[柒号华仔]

个人信条:星光不问赶路人,岁月不负有心人。

个人方向:专注于5G领域,同时兼顾其他网络协议,编解码协议,C/C++,linux等,感兴趣的小伙伴可以关注我,一起交流。


1. 希尔排序介绍

1.1 定义

希尔排序由希尔(Donald Shell)在 1959 年所发表的论文“A high-speed sorting procedure”中提出,因此便以其名字进行命名。

希尔排序的基本思想是先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序,待整个序列中的记录"基本有序"时,再对全体记录进行依次直接插入排序。

1.2 基本原理

希尔排序基本原理为:

  1. 对于一个长度为len的待排序数组,先确定一个初始增量d,通常d=len/2,当然也可以是其他值;
  2. 将数组按照间隔d进行分组,每次间隔距离d取一个元素,取出来的元素放在一个组中;
  3. 当一轮分完后,从第二个元素开始依然间隔d进行分组,直至所有元素分组完毕;
  4. 对每组中的元素进行直接插入排序;
  5. 依次选择一个比d小的增量,通常为len/4,len/8...,重复步骤2~4;
  6. 直到增量减小到1,整个要排序的数被分成一组,排序完成。

1.3 时间复杂度何空间复杂度

希尔排序的时间复杂度为O(n^3/2),希尔排序的时间复杂度与增量序列的选择有关,在有的说明中提到,最好的一个序列是{1,5,19,41,109,...},可以达到O(n^1.3)。

希尔排序与直接插入排序一样,并没有借助中间变量,空间复杂度为O(1)。

1.4 优缺点

优点:希尔排序的时间性能优于直接插入排序,排序速度较快需要的空间小,适合情况复杂的排序。

缺点:非稳定性排序,在不同增量的插入排序过程中,相同的元素可能在各自的插入排序中移动,最后其稳定性就会被打乱。

2.代码实现

2.1 代码设计

a. 实现希尔排序需要设计两层循环,外循环为逐渐减小的增量,内循环为以增量gap为起始,进行分组的组数;

b. 从数组中取出待排元素元素array[i],使用临时变量temp存储其值;

c. 将待排元素array[i]与其同组的array[i-gap]次进行比较,若array[i]大则与array[i-gap]进行交换;

d. 当一轮比对交换完,则将增量再缩小一半,重复b和c的操作,直至gap=0,排序完成。


2.2 代码实现

#include <stdio.h>

void printArray(int array[], int size) {
    int i;
    for (i = 0; i < size; i++) {
        printf("%d ", array[i]);
    }
    printf("\n");
}

int shellSort(int array[],int size)
{
    int i, j, tmp;
    int gap;

    for(gap = size/2;gap > 0;gap /= 2){
        for(i = gap;i < size; i++){
            tmp = array[i];
            j = i - gap;
            while(j >= 0 && tmp < array[j])
            {
                array[j + gap] = array[j];
                j -= gap;
            }
            array[j + gap] = tmp;
        }
    }
}

int main( int argc, int *argv[])
{
    int array[] = {3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};

    shellSort(array,sizeof(array)/sizeof(int));
    printArray(array,sizeof(array)/sizeof(int));

    return 0;
}

运行结果:

image.png

相关文章
|
1月前
|
算法 前端开发 数据处理
小白学python-深入解析一位字符判定算法
小白学python-深入解析一位字符判定算法
48 0
|
1月前
|
存储 算法 Java
解析HashSet的工作原理,揭示Set如何利用哈希算法和equals()方法确保元素唯一性,并通过示例代码展示了其“无重复”特性的具体应用
在Java中,Set接口以其独特的“无重复”特性脱颖而出。本文通过解析HashSet的工作原理,揭示Set如何利用哈希算法和equals()方法确保元素唯一性,并通过示例代码展示了其“无重复”特性的具体应用。
41 3
|
1月前
|
搜索推荐 算法
插入排序算法的平均时间复杂度解析
【10月更文挑战第12天】 插入排序是一种简单直观的排序算法,通过不断将未排序元素插入到已排序部分的合适位置来完成排序。其平均时间复杂度为$O(n^2)$,适用于小规模或部分有序的数据。尽管效率不高,但在特定场景下仍具优势。
|
16天前
|
算法 Linux 定位技术
Linux内核中的进程调度算法解析####
【10月更文挑战第29天】 本文深入剖析了Linux操作系统的心脏——内核中至关重要的组成部分之一,即进程调度机制。不同于传统的摘要概述,我们将通过一段引人入胜的故事线来揭开进程调度算法的神秘面纱,展现其背后的精妙设计与复杂逻辑,让读者仿佛跟随一位虚拟的“进程侦探”,一步步探索Linux如何高效、公平地管理众多进程,确保系统资源的最优分配与利用。 ####
52 4
|
17天前
|
缓存 负载均衡 算法
Linux内核中的进程调度算法解析####
本文深入探讨了Linux操作系统核心组件之一——进程调度器,着重分析了其采用的CFS(完全公平调度器)算法。不同于传统摘要对研究背景、方法、结果和结论的概述,本文摘要将直接揭示CFS算法的核心优势及其在现代多核处理器环境下如何实现高效、公平的资源分配,同时简要提及该算法如何优化系统响应时间和吞吐量,为读者快速构建对Linux进程调度机制的认知框架。 ####
|
1月前
|
前端开发 算法 JavaScript
无界SaaS模式深度解析:算力算法、链接力、数据确权制度
私域电商的无界SaaS模式涉及后端开发、前端开发、数据库设计、API接口、区块链技术、支付和身份验证系统等多个技术领域。本文通过简化框架和示例代码,指导如何将核心功能转化为技术实现,涵盖用户管理、企业店铺管理、数据流量管理等关键环节。
|
1月前
|
机器学习/深度学习 算法 PyTorch
Pytorch-SGD算法解析
SGD(随机梯度下降)是机器学习中常用的优化算法,特别适用于大数据集和在线学习。与批量梯度下降不同,SGD每次仅使用一个样本来更新模型参数,提高了训练效率。本文介绍了SGD的基本步骤、Python实现及PyTorch中的应用示例。
39 0
|
28天前
|
算法 安全 数据安全/隐私保护
基于game-based算法的动态频谱访问matlab仿真
本算法展示了在认知无线电网络中,通过游戏理论优化动态频谱访问,提高频谱利用率和物理层安全性。程序运行效果包括负载因子、传输功率、信噪比对用户效用和保密率的影响分析。软件版本:Matlab 2022a。完整代码包含详细中文注释和操作视频。
|
13天前
|
算法 数据挖掘 数据安全/隐私保护
基于FCM模糊聚类算法的图像分割matlab仿真
本项目展示了基于模糊C均值(FCM)算法的图像分割技术。算法运行效果良好,无水印。使用MATLAB 2022a开发,提供完整代码及中文注释,附带操作步骤视频。FCM算法通过隶属度矩阵和聚类中心矩阵实现图像分割,适用于灰度和彩色图像,广泛应用于医学影像、遥感图像等领域。
|
14天前
|
算法 调度
基于遗传模拟退火混合优化算法的车间作业最优调度matlab仿真,输出甘特图
车间作业调度问题(JSSP)通过遗传算法(GA)和模拟退火算法(SA)优化多个作业在并行工作中心上的加工顺序和时间,以最小化总完成时间和机器闲置时间。MATLAB2022a版本运行测试,展示了有效性和可行性。核心程序采用作业列表表示法,结合遗传操作和模拟退火过程,提高算法性能。

推荐镜像

更多