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

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

相关文章

Spring Security基于数据库验证流程详解

Spring Security 校验流程图 相关解释说明(认真看哦) AbstractAuthenticationProcessingFilter 抽象类 /*** 调用 #requiresAuthentication(HttpServletRequest, HttpServletResponse) 决定是否需要进行验证操作。* 如果需要验证,则会调用 #attemptAuthentica

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例,告诉我们不懂推荐算法的产品,也能从产品侧出发, 设计出一款不错的推荐系统。 相信很多新手产品,看到算法二字,多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法(注:传统是指科班出身的产品都会接触过)。但对于推荐算法,多数产品对着网上搜到的资源,都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后,更是加大了理解的难度。 但,不了解推荐算法,就无法做推荐系

康拓展开(hash算法中会用到)

康拓展开是一个全排列到一个自然数的双射(也就是某个全排列与某个自然数一一对应) 公式: X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。(a[i]在不同应用中的含义不同); 典型应用: 计算当前排列在所有由小到大全排列中的顺序,也就是说求当前排列是第

csu 1446 Problem J Modified LCS (扩展欧几里得算法的简单应用)

这是一道扩展欧几里得算法的简单应用题,这题是在湖南多校训练赛中队友ac的一道题,在比赛之后请教了队友,然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意:把题意转变下就变成了:求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点:求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动,这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升:减少抖动,提高图像的清晰度和细节表现力,使得监控画面更加真实可信。 - 细节增强:在低光条件下,抖

OpenHarmony鸿蒙开发( Beta5.0)无感配网详解

1、简介 无感配网是指在设备联网过程中无需输入热点相关账号信息,即可快速实现设备配网,是一种兼顾高效性、可靠性和安全性的配网方式。 2、配网原理 2.1 通信原理 手机和智能设备之间的信息传递,利用特有的NAN协议实现。利用手机和智能设备之间的WiFi 感知订阅、发布能力,实现了数字管家应用和设备之间的发现。在完成设备间的认证和响应后,即可发送相关配网数据。同时还支持与常规Sof

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

到了这题学会了结构体排序 于是回去修改了 1.2 milking cows 的算法~ 结构体排序核心: 1.结构体定义 struct Milk{int price;int milks;}milk[5000]; 2.自定义的比较函数,若返回值为正,qsort 函数判定a>b ;为负,a<b;为0,a==b; int milkcmp(const void *va,c

poj 3974 and hdu 3068 最长回文串的O(n)解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大,用原来的O(n^2)会爆。 小白上的O(n^2)解法代码:TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO

秋招最新大模型算法面试,熬夜都要肝完它

💥大家在面试大模型LLM这个板块的时候,不知道面试完会不会复盘、总结,做笔记的习惯,这份大模型算法岗面试八股笔记也帮助不少人拿到过offer ✨对于面试大模型算法工程师会有一定的帮助,都附有完整答案,熬夜也要看完,祝大家一臂之力 这份《大模型算法工程师面试题》已经上传CSDN,还有完整版的大模型 AI 学习资料,朋友们如果需要可以微信扫描下方CSDN官方认证二维码免费领取【保证100%免费