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

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

相关文章

Nginx location匹配模式与规则详解

《Nginxlocation匹配模式与规则详解》:本文主要介绍Nginxlocation匹配模式与规则,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、环境二、匹配模式1. 精准模式2. 前缀模式(不继续匹配正则)3. 前缀模式(继续匹配正则)4. 正则模式(大

Android实现在线预览office文档的示例详解

《Android实现在线预览office文档的示例详解》在移动端展示在线Office文档(如Word、Excel、PPT)是一项常见需求,这篇文章为大家重点介绍了两种方案的实现方法,希望对大家有一定的... 目录一、项目概述二、相关技术知识三、实现思路3.1 方案一:WebView + Office Onl

Java实现优雅日期处理的方案详解

《Java实现优雅日期处理的方案详解》在我们的日常工作中,需要经常处理各种格式,各种类似的的日期或者时间,下面我们就来看看如何使用java处理这样的日期问题吧,感兴趣的小伙伴可以跟随小编一起学习一下... 目录前言一、日期的坑1.1 日期格式化陷阱1.2 时区转换二、优雅方案的进阶之路2.1 线程安全重构2

Java中的JSONObject详解

《Java中的JSONObject详解》:本文主要介绍Java中的JSONObject详解,需要的朋友可以参考下... Java中的jsONObject详解一、引言在Java开发中,处理JSON数据是一种常见的需求。JSONObject是处理JSON对象的一个非常有用的类,它提供了一系列的API来操作J

HTML5中的Microdata与历史记录管理详解

《HTML5中的Microdata与历史记录管理详解》Microdata作为HTML5新增的一个特性,它允许开发者在HTML文档中添加更多的语义信息,以便于搜索引擎和浏览器更好地理解页面内容,本文将探... 目录html5中的Mijscrodata与历史记录管理背景简介html5中的Microdata使用M

html5的响应式布局的方法示例详解

《html5的响应式布局的方法示例详解》:本文主要介绍了HTML5中使用媒体查询和Flexbox进行响应式布局的方法,简要介绍了CSSGrid布局的基础知识和如何实现自动换行的网格布局,详细内容请阅读本文,希望能对你有所帮助... 一 使用媒体查询响应式布局        使用的参数@media这是常用的

HTML5表格语法格式详解

《HTML5表格语法格式详解》在HTML语法中,表格主要通过table、tr和td3个标签构成,本文通过实例代码讲解HTML5表格语法格式,感兴趣的朋友一起看看吧... 目录一、表格1.表格语法格式2.表格属性 3.例子二、不规则表格1.跨行2.跨列3.例子一、表格在html语法中,表格主要通过< tab

Linux之计划任务和调度命令at/cron详解

《Linux之计划任务和调度命令at/cron详解》:本文主要介绍Linux之计划任务和调度命令at/cron的使用,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录linux计划任务和调度命令at/cron一、计划任务二、命令{at}介绍三、命令语法及功能 :at

Java使用SLF4J记录不同级别日志的示例详解

《Java使用SLF4J记录不同级别日志的示例详解》SLF4J是一个简单的日志门面,它允许在运行时选择不同的日志实现,这篇文章主要为大家详细介绍了如何使用SLF4J记录不同级别日志,感兴趣的可以了解下... 目录一、SLF4J简介二、添加依赖三、配置Logback四、记录不同级别的日志五、总结一、SLF4J

Java使用ANTLR4对Lua脚本语法校验详解

《Java使用ANTLR4对Lua脚本语法校验详解》ANTLR是一个强大的解析器生成器,用于读取、处理、执行或翻译结构化文本或二进制文件,下面就跟随小编一起看看Java如何使用ANTLR4对Lua脚本... 目录什么是ANTLR?第一个例子ANTLR4 的工作流程Lua脚本语法校验准备一个Lua Gramm