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

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

相关文章

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

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

java实现docker镜像上传到harbor仓库的方式

《java实现docker镜像上传到harbor仓库的方式》:本文主要介绍java实现docker镜像上传到harbor仓库的方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地... 目录1. 前 言2. 编写工具类2.1 引入依赖包2.2 使用当前服务器的docker环境推送镜像2.2

springboot项目打jar制作成镜像并指定配置文件位置方式

《springboot项目打jar制作成镜像并指定配置文件位置方式》:本文主要介绍springboot项目打jar制作成镜像并指定配置文件位置方式,具有很好的参考价值,希望对大家有所帮助,如有错误... 目录一、上传jar到服务器二、编写dockerfile三、新建对应配置文件所存放的数据卷目录四、将配置文

一文详解Java Stream的sorted自定义排序

《一文详解JavaStream的sorted自定义排序》Javastream中的sorted方法是用于对流中的元素进行排序的方法,它可以接受一个comparator参数,用于指定排序规则,sorte... 目录一、sorted 操作的基础原理二、自定义排序的实现方式1. Comparator 接口的 Lam

linux重启命令有哪些? 7个实用的Linux系统重启命令汇总

《linux重启命令有哪些?7个实用的Linux系统重启命令汇总》Linux系统提供了多种重启命令,常用的包括shutdown-r、reboot、init6等,不同命令适用于不同场景,本文将详细... 在管理和维护 linux 服务器时,完成系统更新、故障排查或日常维护后,重启系统往往是必不可少的步骤。本文

gitlab安装及邮箱配置和常用使用方式

《gitlab安装及邮箱配置和常用使用方式》:本文主要介绍gitlab安装及邮箱配置和常用使用方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1.安装GitLab2.配置GitLab邮件服务3.GitLab的账号注册邮箱验证及其分组4.gitlab分支和标签的

C++中零拷贝的多种实现方式

《C++中零拷贝的多种实现方式》本文主要介绍了C++中零拷贝的实现示例,旨在在减少数据在内存中的不必要复制,从而提高程序性能、降低内存使用并减少CPU消耗,零拷贝技术通过多种方式实现,下面就来了解一下... 目录一、C++中零拷贝技术的核心概念二、std::string_view 简介三、std::stri

Linux脚本(shell)的使用方式

《Linux脚本(shell)的使用方式》:本文主要介绍Linux脚本(shell)的使用方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录概述语法详解数学运算表达式Shell变量变量分类环境变量Shell内部变量自定义变量:定义、赋值自定义变量:引用、修改、删

python判断文件是否存在常用的几种方式

《python判断文件是否存在常用的几种方式》在Python中我们在读写文件之前,首先要做的事情就是判断文件是否存在,否则很容易发生错误的情况,:本文主要介绍python判断文件是否存在常用的几种... 目录1. 使用 os.path.exists()2. 使用 os.path.isfile()3. 使用

Mybatis的分页实现方式

《Mybatis的分页实现方式》MyBatis的分页实现方式主要有以下几种,每种方式适用于不同的场景,且在性能、灵活性和代码侵入性上有所差异,对Mybatis的分页实现方式感兴趣的朋友一起看看吧... 目录​1. 原生 SQL 分页(物理分页)​​2. RowBounds 分页(逻辑分页)​​3. Page