插入排序算法

插入排序算法

思想

  • 我们以从小到大的排序进行讲解
  • 插入排序就是将一个元素插入到一个已经是有序的序列中, 通过遍历比较这个待插入元素和有序的序列元素之间的大小,来比较需要插入的位置,使其仍然是一个有序的数组。
  • 数组插入的算法:向后移动元素给待插入的数据位置

详解

  • 第一趟:假设我们需要排序的数组大小为n,一般的思想是先假设第一个元素是有序的,即是已经排序好的,那么第二个元素此时就是待插入的元素,我们拿这个待插入的元素和第一个元素比较大小,如果小的话,那么就将其插入到第一个元素的前面,此时待插入元素就变成了第一个,如果大于的话,就不需要改变位置。那么此时这个数组的前两个元素就是有序的
  • 第二趟: 经过第一趟的,前面两个元素已经是有序的,那么此时的第三个元素就是待插入元素,这个待插入元素先和第二个元素进行比较,如果大于的话,那么就不需要再和第一个元素比较了,当前位置不用改变就可以维持前面三个元素是有序的。如果是小于的话,此时的第二个元素就需要向后移动位置,因为这里可以肯定的是这个待插入元素一定是在其前面插入的,具体的位置没有确定而已。第二个元素向后移动之后,那么此时就需要和第一个元素比较,如果大于的话,那么就插在第一个和第二个元素之间成为当前数组的第二个元素即可,如果小于的话,那么就插入到第一个元素之前,同样的是第一个元素要向后移动为其腾出位置。
  • 第三趟…………………………………第n-1

算法分析

  • 平均时间复杂度:O(n2)
  • 空间复杂度:O(1) (用于记录需要插入的数据)
  • 稳定性:稳定

算法实现 — java

  • 需要注意的是判断条件一定是j>=0&&insertNode<array[j],因为如果调换顺序的话,那么会造成数组下标越界
/*
* 这个是从小到大的插入排序
* @Param array  待排序的数组
*/
public static void insertSort(int[] array){
	//我们假设第一个元素已经是有序的,因此从第二个开始遍历,总共需要遍历n-1次
	for (int i = 1; i < array.length; i++) {
		
		int insertNode=array[i];  //这个就是待插入的数,需要和在之前的元素比较
		
		int j=i-1;   //这个的初始值是待插入数字的前一个数字
		
		//如果待插入的数字比前面的元素小并且此时的j没有到达第一个元素(j>=0)
		//循环结束的条件是insertNode>=array[j],那么此时的insertNode需要插入的位置就是array[j+1]这个位置了
		//需要注意的是&&是短路与的判断,因此需要将j>=0放在前面,否则如果是insertNode<array[j]&&j>=0的形式,那么当j=-1的时候就会造成下标数组越界
		while(j>=0&&insertNode<array[j]){
			array[j+1]=array[j];  //元素后移,以便插入   
			j--;   //比较的元素的下标此时需要前移,和待插入的数据进行比较
		}
		array[j+1]=insertNode;  //这个位置就是待插入元素需要插入的位置
	}
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏PHP在线

PHP字符串和数组操作函数

str_split() 函数把字符串分割到数组中。 stripslashes() 函数删除由 addslashes() 函数添加的反斜杠。 stripcslas...

3847
来自专栏流媒体

C++类大小和静态成员/方法

905
来自专栏黑泽君的专栏

静态变量和成员变量的区别 && 成员变量和局部变量的区别

=============================================================================

1172
来自专栏开发与安全

从零开始学C++之构造函数与析构函数(二):初始化列表(const和引用成员)、拷贝构造函数

一、构造函数初始化列表 推荐在构造函数初始化列表中进行初始化 构造函数的执行分为两个阶段 初始化段 普通计算段 (一)、对象成员及其初始化 #inclu...

2580
来自专栏从零开始学 Web 前端

从零开始学 Web 之 JS 高级(二)原型链,原型的继承

原型链表示的是实例对象与原型对象之间的一种关系,这种关系是通过__proto__原型来联系的。

1133
来自专栏Java帮帮-微信公众号-技术文章全总结

07.Java变量类型

07.Java变量类型 Java 变量类型 在Java语言中,所有的变量在使用前必须声明。声明变量的基本格式如下: ? 格式说明:type为Java数据类型。i...

3767
来自专栏我的博客

Python字符串

# -*- coding: utf-8 -*- import re #字符串替换 str1 = 'hello world world world abc=12...

2996
来自专栏LhWorld哥陪你聊算法

【Scala篇】--Scala中的函数

Scala中的函数还是比较重要的,所以本文章把Scala中可能用到的函数列举如下,并做详细说明。

1751
来自专栏黑泽君的专栏

final关键字、多态、抽象类、接口的小复习

--------------------------------------- 1:final关键字可以干什么?有什么特点?   最终的意思。可以修饰类,方法...

832
来自专栏吾爱乐享

java之学习int和String的相互转换

831

扫码关注云+社区