【C语言 || 排序】希尔排序

2024-06-19 19:28
文章标签 语言 排序 希尔

本文主要是介绍【C语言 || 排序】希尔排序,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

文章目录

    • 前言
    • 1.希尔排序
        • 1.1 直接插入排序
        • 1.2 直接插入排序的实现
          • 1.2.1 直接插入排序的代码实现
        • 1.3 直接插入排序的时间复杂度
        • 1.4 希尔排序
          • 1.4.1 希尔排序概念
          • 1.4.1 希尔排序的代码实现

前言

1.希尔排序

1.1 直接插入排序

在写希尔排序之前,我们需要先了解直接插入排序。直接插入排序是一种简单而稳定的排序算法。它的工作原理是将一个待排序序列分为已排序区间未排序区间,初始时已排序区间只有序列的第一个元素。然后从未排序区间中取出第一个元素,插入到已排序区间的合适位置,使其成为新的已排序区间。重复这个过程,直到未排序区间为空。

图示:

在这里插入图片描述

定义一个变量end,在[0,end]之间是有序的,然后从end+1的位置开始往前比较,一个一个进行比较,(当前是排升序)如果end+1小于end,那就直接让end覆盖住end+1,end+1需要提前记录下来。

1.2 直接插入排序的实现

写排序最好是先写单趟排序,写完之后再开始整体, 定义一个变量end,在[0,end]之间是有序的,单趟排序是将end+1从往[0,end]直接进行插入比较,(当前是需要排升序),end+1如果大于end,就直接让end覆盖end+1。

1.2.1 直接插入排序的代码实现
void InsertSort(int* a,int n)
{for(int i = 0; i < n - 1 ; i++){int end = i;int tmp = a[end + 1];while(end>=0){if(tmp < a[end]){a[end + 1] = a[end];end--;}else{break;}}a[end+1] = tmp;}
}
1.3 直接插入排序的时间复杂度

最差是O(N^2),就是逆序的时候,所有数都需要进行插入排序。

最好就是O(N) 了,就是有序的情况了,当在有序的时候,只需要遍历一遍就可以了,不需要进行插入排序。

我们可以思考一下,如何优化。
可以想到如果我们让这个数组前面的那些比较大的数,让它们先到最后是不是就接近有序了。这就是希尔(Donald Shell)从直接插入排序优化的版本,起名为希尔排序。

1.4 希尔排序
1.4.1 希尔排序概念

希尔排序(ShellSort)是一种基于插入排序的算法,它通过比较相距一定间隔的元素来工作,各趟比较所用的间隔随着算法的进行而减小,直到只比较相邻元素的最后一趟排序为止。
希尔排序的基本思想是:先将整个待排序的记录序列分割成为gap份序列分别进行直接插入排序,然后依次缩减gap再进行排序,待整个序列中的记录“基本有序”时,再对全体记录进行一次直接插入排序。

1.预排序.
2.直接插入排序.

当gap==3时,如图所示:
在这里插入图片描述

这样较大的数就交换到了数组的后面,在进行一次直接插入排序就可以排好顺序了。

希尔排序的时间复杂度大概是O(1.25*N^1.26)
空间复杂度是O(1)

1.4.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(tmp < a[end]){a[end + gap] = a[end];end-=gap;}else{break;}}	a[end + gap] = tmp;}}
}

这篇关于【C语言 || 排序】希尔排序的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1075927

相关文章

C语言中的数据类型强制转换

《C语言中的数据类型强制转换》:本文主要介绍C语言中的数据类型强制转换方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录C语言数据类型强制转换自动转换强制转换类型总结C语言数据类型强制转换强制类型转换:是通过类型转换运算来实现的,主要的数据类型转换分为自动转换

利用Go语言开发文件操作工具轻松处理所有文件

《利用Go语言开发文件操作工具轻松处理所有文件》在后端开发中,文件操作是一个非常常见但又容易出错的场景,本文小编要向大家介绍一个强大的Go语言文件操作工具库,它能帮你轻松处理各种文件操作场景... 目录为什么需要这个工具?核心功能详解1. 文件/目录存javascript在性检查2. 批量创建目录3. 文件

C语言实现两个变量值交换的三种方式

《C语言实现两个变量值交换的三种方式》两个变量值的交换是编程中最常见的问题之一,以下将介绍三种变量的交换方式,其中第一种方式是最常用也是最实用的,后两种方式一般只在特殊限制下使用,需要的朋友可以参考下... 目录1.使用临时变量(推荐)2.相加和相减的方式(值较大时可能丢失数据)3.按位异或运算1.使用临时

使用C语言实现交换整数的奇数位和偶数位

《使用C语言实现交换整数的奇数位和偶数位》在C语言中,要交换一个整数的二进制位中的奇数位和偶数位,重点需要理解位操作,当我们谈论二进制位的奇数位和偶数位时,我们是指从右到左数的位置,本文给大家介绍了使... 目录一、问题描述二、解决思路三、函数实现四、宏实现五、总结一、问题描述使用C语言代码实现:将一个整

C++快速排序超详细讲解

《C++快速排序超详细讲解》快速排序是一种高效的排序算法,通过分治法将数组划分为两部分,递归排序,直到整个数组有序,通过代码解析和示例,详细解释了快速排序的工作原理和实现过程,需要的朋友可以参考下... 目录一、快速排序原理二、快速排序标准代码三、代码解析四、使用while循环的快速排序1.代码代码1.由快

C语言字符函数和字符串函数示例详解

《C语言字符函数和字符串函数示例详解》本文详细介绍了C语言中字符分类函数、字符转换函数及字符串操作函数的使用方法,并通过示例代码展示了如何实现这些功能,通过这些内容,读者可以深入理解并掌握C语言中的字... 目录一、字符分类函数二、字符转换函数三、strlen的使用和模拟实现3.1strlen函数3.2st

Go语言中最便捷的http请求包resty的使用详解

《Go语言中最便捷的http请求包resty的使用详解》go语言虽然自身就有net/http包,但是说实话用起来没那么好用,resty包是go语言中一个非常受欢迎的http请求处理包,下面我们一起来学... 目录安装一、一个简单的get二、带查询参数三、设置请求头、body四、设置表单数据五、处理响应六、超

C语言中的浮点数存储详解

《C语言中的浮点数存储详解》:本文主要介绍C语言中的浮点数存储详解,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1、首先明确一个概念2、接下来,讲解C语言中浮点型数存储的规则2.1、可以将上述公式分为两部分来看2.2、问:十进制小数0.5该如何存储?2.3 浮点

基于Python实现多语言朗读与单词选择测验

《基于Python实现多语言朗读与单词选择测验》在数字化教育日益普及的今天,开发一款能够支持多语言朗读和单词选择测验的程序,对于语言学习者来说无疑是一个巨大的福音,下面我们就来用Python实现一个这... 目录一、项目概述二、环境准备三、实现朗读功能四、实现单词选择测验五、创建图形用户界面六、运行程序七、

使用Go语言开发一个命令行文件管理工具

《使用Go语言开发一个命令行文件管理工具》这篇文章主要为大家详细介绍了如何使用Go语言开发一款命令行文件管理工具,支持批量重命名,删除,创建,移动文件,需要的小伙伴可以了解下... 目录一、工具功能一览二、核心代码解析1. 主程序结构2. 批量重命名3. 批量删除4. 创建文件/目录5. 批量移动三、如何安