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

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

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

个人方向:专注于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

相关文章
|
19天前
|
算法 前端开发 数据处理
小白学python-深入解析一位字符判定算法
小白学python-深入解析一位字符判定算法
38 0
|
12天前
|
存储 算法 Java
解析HashSet的工作原理,揭示Set如何利用哈希算法和equals()方法确保元素唯一性,并通过示例代码展示了其“无重复”特性的具体应用
在Java中,Set接口以其独特的“无重复”特性脱颖而出。本文通过解析HashSet的工作原理,揭示Set如何利用哈希算法和equals()方法确保元素唯一性,并通过示例代码展示了其“无重复”特性的具体应用。
30 3
|
13天前
|
搜索推荐 算法
插入排序算法的平均时间复杂度解析
【10月更文挑战第12天】 插入排序是一种简单直观的排序算法,通过不断将未排序元素插入到已排序部分的合适位置来完成排序。其平均时间复杂度为$O(n^2)$,适用于小规模或部分有序的数据。尽管效率不高,但在特定场景下仍具优势。
|
19天前
|
机器学习/深度学习 算法 PyTorch
Pytorch-RMSprop算法解析
关注B站【肆十二】,观看更多实战教学视频。本期介绍深度学习中的RMSprop优化算法,通过调整每个参数的学习率来优化模型训练。示例代码使用PyTorch实现,详细解析了RMSprop的参数及其作用。适合初学者了解和实践。
29 1
|
14天前
|
前端开发 算法 JavaScript
无界SaaS模式深度解析:算力算法、链接力、数据确权制度
私域电商的无界SaaS模式涉及后端开发、前端开发、数据库设计、API接口、区块链技术、支付和身份验证系统等多个技术领域。本文通过简化框架和示例代码,指导如何将核心功能转化为技术实现,涵盖用户管理、企业店铺管理、数据流量管理等关键环节。
|
19天前
|
机器学习/深度学习 算法 PyTorch
Pytorch-SGD算法解析
SGD(随机梯度下降)是机器学习中常用的优化算法,特别适用于大数据集和在线学习。与批量梯度下降不同,SGD每次仅使用一个样本来更新模型参数,提高了训练效率。本文介绍了SGD的基本步骤、Python实现及PyTorch中的应用示例。
26 0
|
19天前
|
机器学习/深度学习 传感器 算法
Pytorch-Adam算法解析
肆十二在B站分享深度学习实战教程,本期讲解Adam优化算法。Adam结合了AdaGrad和RMSProp的优点,通过一阶和二阶矩估计,实现自适应学习率,适用于大规模数据和非稳态目标。PyTorch中使用`torch.optim.Adam`轻松配置优化器。
30 0
|
19天前
|
缓存 Java 程序员
Map - LinkedHashSet&Map源码解析
Map - LinkedHashSet&Map源码解析
39 0
|
19天前
|
算法 Java 容器
Map - HashSet & HashMap 源码解析
Map - HashSet & HashMap 源码解析
29 0
|
19天前
|
存储 Java C++
Collection-PriorityQueue源码解析
Collection-PriorityQueue源码解析
33 0

推荐镜像

更多