直接插入排序(Straight Insertion Sort)

简介: 直接插入排序

一、简单释义

1、算法概念

 对插入第i个记录时,R1、R2、…、Ri-1均已排好顺序。因此,将第i个记录Ri-1、…、R2、R1进行比较,找到合适的位置插入,他简单明了但是速度很慢。

2、算法目的

 把无序数组通过彼此之间比较进行移动形成一个有序数组

3、算法思想

 将一个记录插入到已经排好序的有序表中,从而一个新的并且记录数增1的有序表。

二、核心思想

旧–已经排序好的有序表;

新–有序表插入一个新的记录,形成一个新的有序表;

三、图形展示

f35fdfac1f704fe4a6c91f1e62a931e7.png

 1、第一次排序:首先2和8进行比较,8比2大所以不交换位置。

 2、第二次排序:首先1和8进行比较,1比8小所以交换位置,然后1和2进行比较,1比2小交换位置。

 3、第三次排序:首先4和8进行比较,4比8小所以交换位置,然后4和2进行比较,4比2大不交换位置,最后4和1进行比较,4比1大不交换位置。

 4、第四次排序:首先9和8进行比较,9比8大所以不交换位置,后面以此类推。

四、代码实现

/**
 * @BelongsProject: demo
 * @BelongsPackage: com.wzl.Algorithm.Partition
 * @Author: Wuzilong
 * @Description: 直接插入排序
 * @CreateTime: 2023-04-26 09:27
 * @Version: 1.0
 */
public class InsertionSort {
    public static void insertionSort(int[] num){
        for (int i =1; i<num.length;i++){
            if (num[i]<num[i-1]){
                int temp=num[i];
                for (int j=i; j>=0;j--){
                    if (j>0&&num[j-1]>temp){
                        num[j]=num[j-1];
                    }else{
                        num[j]=temp;
                        break;
                    }
                }
            }
            System.out.println(Arrays.toString(num));
        }
    }
    public static void main(String[] args) {
        int[] num={2,8,1,4,9,5,7};
        insertionSort(num);
    }

运行结果

da881d69366149fd9470ea7a3353964c.png

五、算法描述

1、问题描述

 每一步将一个待排序的元素,按其排序码的大小,插入到前面已经排好序的一组元素的适当位置上去,直到元素全部插入为止

2、算法过程

整个算法过程分为以下几步:

 1)每次从无序表中取出第一个元素,把它插入到有序表的合适位置,使有序表仍然有序。

 2)第一趟比较前两个数,然后把第二个数按大小插入到有序表中。

 3)第二趟把第三个数据与前两个数从后向前比较,把第三个数按大小插入到有序表中。

 4)依次进行下去,进行了(n-1)趟比较以后就完成了整个排序过程。

3、算法总结

 直接插入排序是由两层嵌套循环组成的。外层循环标识并决定待比较的数值。内层循环为待比较数值确定其最终位置。直接插入排序将待比较的数值与它的前一个数值进行比较,所以外层循环是从第二个数值开始的。当前一数值比待比较数值大的情况下继续循环比较,直到找到比待比较数值小的并将待比较数值置入其后一位置,结束该次循环。

六、算法分析

1、时间复杂度

 首先直接插入排序是一个稳定的排序算法;最好的情况下,也就是排序本身是有序的,共需比较n-1次,因为没有移动的记录,时间复杂度为O(n)。最坏的情况下,即排序表是逆序的情况,时间复杂为O(n²)。

2、空间复杂度

 算法的空间复杂度并不是计算实际占用的空间,而是计算整个算法的辅助空间单元的个数。在直接插入排序中只使用了i,j,temp这三个辅助空间单元,所以空间复杂度是O(1)。


相关文章
|
存储 网络协议 安全
部署打印服务(一)
部署打印服务(一)
771 0
|
8月前
|
机器学习/深度学习 算法 PyTorch
DeepSeek 背后的技术:GRPO,基于群组采样的高效大语言模型强化学习训练方法详解
强化学习(RL)是提升大型语言模型(LLM)推理能力的重要手段,尤其在复杂推理任务中表现突出。DeepSeek团队通过群组相对策略优化(GRPO)方法,在DeepSeek-Math和DeepSeek-R1模型中取得了突破性成果,显著增强了数学推理和问题解决能力。GRPO无需价值网络,采用群组采样和相对优势估计,有效解决了传统RL应用于语言模型时的挑战,提升了训练效率和稳定性。实际应用中,DeepSeek-Math和DeepSeek-R1分别在数学推理和复杂推理任务中展现了卓越性能。未来研究将聚焦于改进优势估计、自适应超参数调整及理论分析,进一步拓展语言模型的能力边界。
1113 8
DeepSeek 背后的技术:GRPO,基于群组采样的高效大语言模型强化学习训练方法详解
|
存储 Cloud Native 关系型数据库
PolarDB 高可用架构设计与实践
【8月更文第27天】 在现代互联网应用中,数据库作为核心的数据存储层,其稳定性和可靠性尤为重要。阿里云的 PolarDB 作为一款云原生的关系型数据库服务,提供了高可用、高性能和自动化的特性,适用于各种规模的应用。本文将详细介绍 PolarDB 的高可用架构设计,并探讨其实现数据安全性和业务连续性的关键技术。
372 0
|
计算机视觉
5.1.2.3 目标检测基本概念和YOLOv3设计思想——交并比 NMS
这篇文章详细解释了目标检测中的关键概念交并比(IoU)和非极大值抑制(NMS),包括它们的定义、计算方法和在目标检测中的应用,以及如何使用这些技术来优化预测结果和减少冗余预测框。
|
5G UED
5G NR中的寻呼过程是如何工作的?
【8月更文挑战第31天】
525 0
|
存储 负载均衡 容灾
架构设计|基于 raft-listener 实现实时同步的主备集群
本文介绍如何从数据库内核角度建立一套实时同步的主备集群,确保线上业务的高可用性和可靠性。本系统采用双 AZ 主备容灾机制,并要求数据与 schema 实时同步,同步时延平均在 1 秒内,p99 在 2 秒内。此外,系统支持高效的自动或手动主备切换,并能在切换过程中恢复丢失数据。
322 0
|
定位技术
vue-baidu-map 报错 | BMap is undefined
vue-baidu-map 报错 | BMap is undefined
300 1
QT取消标题栏,如何实现窗口移动
QT取消标题栏,如何实现窗口移动
181 0
|
存储 JavaScript Linux
百度搜索:蓝易云【CentOS 8上使用NVM安装特定版本的Node.js教程】
现在,你已成功安装和切换到特定版本的Node.js。希望这个教程能够帮助你在CentOS 8上使用NVM安装特定版本的Node.js。
280 2