排序方式汇总(一)--插入排序

2024-08-26 01:32

本文主要是介绍排序方式汇总(一)--插入排序,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

    插入排序算法主要有直接插入排序算法、折半查找算法、希尔插入排序算法。


·直接插入排序:

将记录插到已排好的有序表中,从而得到一个新的、记录数量增1的有序表。

【算法思想】

1)设待排序的记录存放在数组r[1..n],r[1]是一个有序序列。

2)循环n-1次,每次使用顺序查找法,查找r[i](i=2,3...,n)在已排好的序列r[1..i-1]中的插入位置,然后将r[i]插入表厂为i-1的有序序列r[1..i-1]直到将r[n]插入表厂为n-1的有序序列r[1..n-1],最后得到一个表长尾n的有序序列。

如下图所示待排序记录的关键字序列为{49,38,65,97,13,27,49}使用直接插入排序法进行排序的过程:


【算法描述】

void InsertSort (SqList &L){//对顺序表L做直接插入排序for(i=2;i<=L.length;++i)if(L.r[i].key<L.r[i-1].key){//实现r[i]插入有序表L.r[0]=L.r[i];//将待插入的记录暂存到监视哨中L.r[i]=L.r[i-1];//r[i-1]向后移动for(j=i-2;:L.r[0].key<L.r[j].key;--j)//从后向前寻找插入位置L.r[j+1}=L.r[j];//记录逐个后移,直到找到插入位置L.r[j+1]=L.r[0];//将r[0]即原r[i],插入到正确位置}
}

【算法特点】

1)是稳定排序

2)算法简单,容易实现

3)也适用于链式存储结构,知识在单链表上不是移动记录,只要修改相应的指针。

4)更适合于初始记录基本有序的情况,当初始记录无序,n较大时,此算法时间复杂度较高,不宜采用。


·折半插入排序

利用“折半查找”来实现的排序算法。

【算法思想】

1)将待排序的记录存放在数组r[1..n]中,r[1]是一个有序序列。

2)循环n-1次,每次使用折半查找法,查找r[i](i=2,3,..n)在已排好的序列r[1..i-1],直到将r[n]插入表长为n-1的有序序列r[1..n-1],最后得到一个表长为n的有序序列。

看下面一个小例子:


【算法描述】

void BInsertSort(SqList &L){//对顺序表L做折半查找for(i=2;i<=L.length;++i){L.r[0]=L.r[i];//将待插入的记录暂存到监视哨中low=1;high=i-1;//置查找区间初值while(low<=high){//在r[row..high]中折半查找插入位置m=(low+high)/2;//折半if(L.r[0].key<L.r[m].key)high=m-1;//插入点在前一子表else low=m+1;//插入点在后面子表}for(j=i-1;j>high+1;--)L.r[j+1]=L.r[j];//记录后移L.r[high+1]=L.r[0];//将r[0]即原r[i],插入到正确位置}
}
【算法特点】

1)是稳定的

2)因为要进行折半查找,所以只能用于顺序结构,不能用于链式结构

3)适合初始记录无序,n较大时的情况。


·希尔排序

希尔排序又称“缩小增量排序”是插入排序的一种。

【算法思想】

希尔排序实质上是采用分组插入的方法。先将整个待排序记录序列分割成几组,从而减少参与直接超人排序的数据量,对每组分别进行直接插入排序,然后增加每组的数据量,重新分组。

如下实例:


【算法描述】

void ShellInsert(SqList &L,int dk){//对顺序表L做一趟增量是dk的希尔插入排序for(i=dk+1;i<L.length;++i)if(L.r[i].key<L.r[i-dk].key){//需将L.r[i]插入有序增量表L.r[0]=L.r[i];//暂存在r[0]for(j=i-dk;j>0&&L.r[0].key<L.r[j].key;j-=dk)L.r[j+dk]=L.r[j];//记录后移,直到找到插入位置L.r[j+dk]=L.r[0];}
}
void ShellSort(SqList &L,int dt[],int t){for(k=0;k<t;++k)ShellInsert(L,dt[k]);//一趟增量为dt[t]的希尔排序
}
【算法特点】

1)记录跳跃式第移动导致排序算法是不稳定的

2)只能用于顺序结构,不能用于链式结构

3)增量序列可以有多种取法,但应该使增量序列中的值没有除1之外的公因式,并且最后一个增量值必须等于1

4)记录总的比较次数和移动次数都比直接插入排序要少,n越大时,效果越明显。


【小结】

总之,插入排序的基本思想是,每一趟将一个待排序的记录,按其关键字的大小插入到已经排好序的一组记录的适当位置上,直到所有待排序记录全部插入为止。

这篇关于排序方式汇总(一)--插入排序的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

Python实现终端清屏的几种方式详解

《Python实现终端清屏的几种方式详解》在使用Python进行终端交互式编程时,我们经常需要清空当前终端屏幕的内容,本文为大家整理了几种常见的实现方法,有需要的小伙伴可以参考下... 目录方法一:使用 `os` 模块调用系统命令方法二:使用 `subprocess` 模块执行命令方法三:打印多个换行符模拟

RabbitMQ消息总线方式刷新配置服务全过程

《RabbitMQ消息总线方式刷新配置服务全过程》SpringCloudBus通过消息总线与MQ实现微服务配置统一刷新,结合GitWebhooks自动触发更新,避免手动重启,提升效率与可靠性,适用于配... 目录前言介绍环境准备代码示例测试验证总结前言介绍在微服务架构中,为了更方便的向微服务实例广播消息,

SpringBoot中六种批量更新Mysql的方式效率对比分析

《SpringBoot中六种批量更新Mysql的方式效率对比分析》文章比较了MySQL大数据量批量更新的多种方法,指出REPLACEINTO和ONDUPLICATEKEY效率最高但存在数据风险,MyB... 目录效率比较测试结构数据库初始化测试数据批量修改方案第一种 for第二种 case when第三种

Linux线程之线程的创建、属性、回收、退出、取消方式

《Linux线程之线程的创建、属性、回收、退出、取消方式》文章总结了线程管理核心知识:线程号唯一、创建方式、属性设置(如分离状态与栈大小)、回收机制(join/detach)、退出方法(返回/pthr... 目录1. 线程号2. 线程的创建3. 线程属性4. 线程的回收5. 线程的退出6. 线程的取消7.

golang程序打包成脚本部署到Linux系统方式

《golang程序打包成脚本部署到Linux系统方式》Golang程序通过本地编译(设置GOOS为linux生成无后缀二进制文件),上传至Linux服务器后赋权执行,使用nohup命令实现后台运行,完... 目录本地编译golang程序上传Golang二进制文件到linux服务器总结本地编译Golang程序

Linux下删除乱码文件和目录的实现方式

《Linux下删除乱码文件和目录的实现方式》:本文主要介绍Linux下删除乱码文件和目录的实现方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录linux下删除乱码文件和目录方法1方法2总结Linux下删除乱码文件和目录方法1使用ls -i命令找到文件或目录

Linux在线解压jar包的实现方式

《Linux在线解压jar包的实现方式》:本文主要介绍Linux在线解压jar包的实现方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录linux在线解压jar包解压 jar包的步骤总结Linux在线解压jar包在 Centos 中解压 jar 包可以使用 u

Jenkins分布式集群配置方式

《Jenkins分布式集群配置方式》:本文主要介绍Jenkins分布式集群配置方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1.安装jenkins2.配置集群总结Jenkins是一个开源项目,它提供了一个容易使用的持续集成系统,并且提供了大量的plugin满

Java通过驱动包(jar包)连接MySQL数据库的步骤总结及验证方式

《Java通过驱动包(jar包)连接MySQL数据库的步骤总结及验证方式》本文详细介绍如何使用Java通过JDBC连接MySQL数据库,包括下载驱动、配置Eclipse环境、检测数据库连接等关键步骤,... 目录一、下载驱动包二、放jar包三、检测数据库连接JavaJava 如何使用 JDBC 连接 mys

C#读写文本文件的多种方式详解

《C#读写文本文件的多种方式详解》这篇文章主要为大家详细介绍了C#中各种常用的文件读写方式,包括文本文件,二进制文件、CSV文件、JSON文件等,有需要的小伙伴可以参考一下... 目录一、文本文件读写1. 使用 File 类的静态方法2. 使用 StreamReader 和 StreamWriter二、二进