十大经典排序算法——插入排序与希尔排序(超详解)

2024-06-23 06:20

本文主要是介绍十大经典排序算法——插入排序与希尔排序(超详解),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

一、插入排序

1.基本思想

直接插入排序是一种简单的插入排序法,基本思想是:把待排序的记录按其数值的大小逐个插入到一个已经排好序的有序序列中,直到所有的记录插入完为止,得到一个新的有序序列。

2.直接插入排序

当插入第 end + 1 个元素时,前面的arr[0],arr[1],...  ,arr[end]已经排好序,此时用arr[end + 1]的值与arr[end],arr[end - 1],... 的值进行比较,找到插入位置将arr[end + 1]插入,原来位置上的元素顺序后移。

3.图示

3.时间复杂度:

时间复杂的一般是看最坏的情况

最坏的情况—逆序,时间复杂度:O(N^{2})

最好的情况—顺序,时间复杂度为:O(N)

4.直接插入排序特性总结

(1)元素集合越接近有序,直接插入排序算法的时间效率越高

(2)时间复杂度:O(N^{2})

(3)空间复杂度:O(1),是一种稳定的排序算法

(4)稳定性:稳定 

5.参考代码

//插入排序
void InsertSort(int* arr, int n)
{for (int i = 0; i < n-1; i++){//[0,end]是有序的,end + 1位置的值插入到[0,end],保持有序int end = i;int tmp = arr[end + 1];while (end >= 0){if (tmp < arr[end]){arr[end + 1] = arr[end];end--;}else{break;}}arr[end + 1] = tmp;}
}

二、希尔排序

1.基本思想

希尔排序又称缩小增量法, 希尔排序的基本思想是:现有选定一个整数gap,把待排序的文件中所有记录分成几个组,所有距离为gap的记录分在同一组内,并对每一组内的记录进行排序。然后,重复上述分组和排序的工作。直到gap==1时,所有记录在同一组内排好序

2.操作

(1)预排序(让数组接近有序)

(2)插入排序 

思想:根据给出的整数gap,将数组分组,再分别对这些组进行插入排序

gap > 1 是预排序,gap == 1 是插入排序 

gap越大,大的数可以越快跳到后面,小的数可以越快跳到前面,得到的数据也越不接近有序。

gap越小,跳的越慢,也越接近有序。当gap是1,相当于插入排序。

代码实现: 两种方式

int gap = 3;
//多组并着走
for (int i = 0; i < n - gap; ++i)
{int end = i;int tmp = arr[end + gap];while (end >= 0){if (tmp < arr[end]){arr[end + gap] = arr[end];end -= gap;}else{break;}}arr[end + gap] = tmp;
}	
int gap = 3;
//一组一组走
for (int j = 0; j < gap; j++)
{for (int i = 0; i < n - gap; i += gap){int end = i;int tmp = arr[end + gap];while (end >= 0){if (tmp < arr[end]){arr[end + gap] = arr[end];end -= gap;}else{break;}}arr[end + gap] = tmp;}
}

3.如何选择希尔增量

希尔排序的分析是个复杂的问题,因为它的时间是所取“增量”序列的函数,者设计一些数学上尚未接轨的难题。因此,到目前为止尚未有人求得一种最好的增量序列,但大量的研究已经得出一些局部的结论。如有人指出,当增量序列为dlta[k]= 2^{t-k+1}-1时,希尔排序的时间复杂度为O(N^{\frac{3}{2}}),其中t为排序趟数,1\leqslant k\leqslant t\leqslant \left \lfloor{log_{2}}^{(n+1)}\right \rfloor。还有人在大量的实验中推出:当n在某个特定范围内,希尔排序所需的比较和移动次数越为n^{1.3},当n\rightarrow∞时,可减少到n({log_{}}^{n})^{2^{\left \lfloor 2 \right \rfloor}}。增量序列可以有各种取法,但需要注意:应是增量序列中的值没有除以1以外的公因子,并且最后一个增量值必须等于1。

gap的取值有多种。最初Shell提出取gap= \left \lfloor n/2 \right \rfloorgap= \left \lfloor gap/2 \right \rfloor,直到gap= 1,后来Knuth提出取gap= \left \lfloor gap/3 \right \rfloor + 1。(+1是为了保证最后一个gap的值是1) 

在Knuth所著的《计算机程序设计技巧》中,利用大量的实验统计资料得出,当n很大时,关进码平均比较次数和对象平均移动次数大约在n^{1.25}1.6n^{1.25}范围内,这是利用直接插入排序作为子序列排序方法的情况下得到的。

4.希尔排序完整图示: 

gap = gap / 3 + 1(+1是为了保证最后一个gap的值是1) 

5.希尔排序的特性总结 

(1)希尔排序是对直接插入排序的优化

(2)当gap > 1时都是预排序,目的是让数组更接近与有序。当gap == 1时,数组已经接近有序了,这样就会很快。对整体而言,可以达到优化的效果。

(3)希尔排序的时间复杂度不好计算,因为gap的取值方式有很多种,导致难以计算。    大约是在O(N^{1.3})左右。

理解一下过程:

(4)稳定性:不稳定

6.代码实现 

void SellSort(int* arr, 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 = arr[end + gap];while (end >= 0){if (tmp < arr[end]){arr[end + gap] = arr[end];end -= gap;}else{break;}}arr[end + gap] = tmp;}	}
}

三、排序效率对比

将插入排序,希尔排序,堆排序的运行效率进行对比

http://t.csdnimg.cn/QtpwY堆排序详解在这篇文章!

void TestOP()
{srand(time(0));const int N = 100000;int* a1 = (int*)malloc(sizeof(int) * N);int* a2 = (int*)malloc(sizeof(int) * N);int* a3 = (int*)malloc(sizeof(int) * N);for (int i = 0; i < N; ++i){a1[i] = rand();a2[i] = a1[i];a3[i] = a1[i];}int begin1 = clock();InsertSort(a1, N);int end1 = clock();int begin2 = clock();SellSort(a2, N);int end2 = clock();int begin4 = clock();HPSort(a4, N);int end4 = clock();printf("InsertSort:%d\n", end1 - begin1);printf("ShellSort:%d\n", end2 - begin2);printf("HPSort:%d\n", end4 - begin4);free(a1);free(a2);free(a3);
}int main()
{int arr[] = { 9,1,2,5,7,4,6,3,8 };int sz = sizeof(arr) / sizeof(arr[0]);TestOP();return 0;
}

上图为代码运行结果,同样是十万个随机数,插入排序相较于希尔排序和堆排序就逊色一些。

这篇关于十大经典排序算法——插入排序与希尔排序(超详解)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

C#数据结构之字符串(string)详解

《C#数据结构之字符串(string)详解》:本文主要介绍C#数据结构之字符串(string),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录转义字符序列字符串的创建字符串的声明null字符串与空字符串重复单字符字符串的构造字符串的属性和常用方法属性常用方法总结摘

Java中StopWatch的使用示例详解

《Java中StopWatch的使用示例详解》stopWatch是org.springframework.util包下的一个工具类,使用它可直观的输出代码执行耗时,以及执行时间百分比,这篇文章主要介绍... 目录stopWatch 是org.springframework.util 包下的一个工具类,使用它

Java进行文件格式校验的方案详解

《Java进行文件格式校验的方案详解》这篇文章主要为大家详细介绍了Java中进行文件格式校验的相关方案,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录一、背景异常现象原因排查用户的无心之过二、解决方案Magandroidic Number判断主流检测库对比Tika的使用区分zip

Java实现时间与字符串互相转换详解

《Java实现时间与字符串互相转换详解》这篇文章主要为大家详细介绍了Java中实现时间与字符串互相转换的相关方法,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录一、日期格式化为字符串(一)使用预定义格式(二)自定义格式二、字符串解析为日期(一)解析ISO格式字符串(二)解析自定义

springboot security快速使用示例详解

《springbootsecurity快速使用示例详解》:本文主要介绍springbootsecurity快速使用示例,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝... 目录创www.chinasem.cn建spring boot项目生成脚手架配置依赖接口示例代码项目结构启用s

Python中随机休眠技术原理与应用详解

《Python中随机休眠技术原理与应用详解》在编程中,让程序暂停执行特定时间是常见需求,当需要引入不确定性时,随机休眠就成为关键技巧,下面我们就来看看Python中随机休眠技术的具体实现与应用吧... 目录引言一、实现原理与基础方法1.1 核心函数解析1.2 基础实现模板1.3 整数版实现二、典型应用场景2

一文详解SpringBoot响应压缩功能的配置与优化

《一文详解SpringBoot响应压缩功能的配置与优化》SpringBoot的响应压缩功能基于智能协商机制,需同时满足很多条件,本文主要为大家详细介绍了SpringBoot响应压缩功能的配置与优化,需... 目录一、核心工作机制1.1 自动协商触发条件1.2 压缩处理流程二、配置方案详解2.1 基础YAML

Python实现无痛修改第三方库源码的方法详解

《Python实现无痛修改第三方库源码的方法详解》很多时候,我们下载的第三方库是不会有需求不满足的情况,但也有极少的情况,第三方库没有兼顾到需求,本文将介绍几个修改源码的操作,大家可以根据需求进行选择... 目录需求不符合模拟示例 1. 修改源文件2. 继承修改3. 猴子补丁4. 追踪局部变量需求不符合很

java中反射(Reflection)机制举例详解

《java中反射(Reflection)机制举例详解》Java中的反射机制是指Java程序在运行期间可以获取到一个对象的全部信息,:本文主要介绍java中反射(Reflection)机制的相关资料... 目录一、什么是反射?二、反射的用途三、获取Class对象四、Class类型的对象使用场景1五、Class

golang 日志log与logrus示例详解

《golang日志log与logrus示例详解》log是Go语言标准库中一个简单的日志库,本文给大家介绍golang日志log与logrus示例详解,感兴趣的朋友一起看看吧... 目录一、Go 标准库 log 详解1. 功能特点2. 常用函数3. 示例代码4. 优势和局限二、第三方库 logrus 详解1.