温馨提示×

温馨提示×

您好,登录后才能下订单哦!

密码登录×
登录注册×
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》

好程序员Java培训分享Java常见排序算法之插入排序

发布时间:2020-08-11 21:27:11 来源:ITPUB博客 阅读:134 作者:好程序员 栏目:编程语言

好程序员Java培训分享Java常见排序算法之插入排序,之前我们说过排序是算法中的一部分。所以我们学习排序也是算法的入门,为了能让大家感受到排序是算法的一部分,我举个例子证明一下:比如麻 将游戏,发完牌之后需要对手上的牌进行排序,大家想想,麻 将排序如何排呢?它有什么特点呢?而且在摸牌打 牌的过程中,我们要不断的排序,如何排序呢?选择什么排序算法最快呢?

以上这种情况我们就可以分析选择哪种排序算法更高效。比如下图已经有一副固定顺序的牌了:

好程序员Java培训分享Java常见排序算法之插入排序

此时轮到我们摸牌,摸到的牌如下:

好程序员Java培训分享Java常见排序算法之插入排序

此时,要将这个“三同”放到上面的一副牌中,就存在如下规律:

1、正常“3同”应该放到“2同”和”4同“中间。

2、跟其他花色的牌没有关系,甚至跟”5同“也没有关系。只需要把”3同“放到”2同“和”4同“中间就行。至于”2同”和”4同”在哪里不要紧。

我们前面学习了选择排序,如果使用选择排序对上面这副牌进行排序是否合适呢?显然是不合适的,因为选择排序必须从“七万”开始比较,选择最小牌跟头一张牌交换位置,依次类推。但是此处麻 将牌的“3同”跟”七万“没有关系,不需要影响”7万“。所以使用选择排序不合适,因为时间负责度很高;此处使用插入排序会更好,什么是插入排序呢?就是本节需要介绍的内容。

二、插入排序

插入排序属于简单排序的一种,通常指的简单排序只是因为其算法思路比较容易理解,不代表其用途很简单。为了让大家掌握插入排序,我们先看看插入排序的原理。

2.1、插入排序的原理

首先有一个待排序的数组如下:

好程序员Java培训分享Java常见排序算法之插入排序

以上数组中只有一个数字0的顺序需要排列,其他数字的顺序都是对的。这种数组使用插入排序的效率更高,下面介绍此数组使用插入排序的流程。

1、先比较1和2,如果2比1小则交换位置。否则不交换位置。此数组不需要交换位置。

好程序员Java培训分享Java常见排序算法之插入排序

2、再比较2和3,如果3比2小,则交换位置。但是实际3比2大所以不交换位置,保持不变。

好程序员Java培训分享Java常见排序算法之插入排序

3、同理,3和4比较也不需要交换位置,保持不变

好程序员Java培训分享Java常见排序算法之插入排序

4、接来下,4和0比较,0小于4,所以交换位置

好程序员Java培训分享Java常见排序算法之插入排序

交换位置之后的数组如下:

好程序员Java培训分享Java常见排序算法之插入排序

5、因为3的邻居发生变化,所以3和0再次比较,0比3小,交换位置,交换之后的数组如下:

好程序员Java培训分享Java常见排序算法之插入排序

6、依次类推,0分别和2交换位置之后的数组如下:

好程序员Java培训分享Java常见排序算法之插入排序

0再和1交换位置的数组如下:

好程序员Java培训分享Java常见排序算法之插入排序

这样一个数组的顺序就对了,但是循环还没有完成,因为我们刚才仅仅循环到数字4这个位置,数字5还没有比较。

7、最后比较4和5,如果5比4小则交换位置,但是5比4大,所以位置不变。数组循环完毕,最终排序如下:

好程序员Java培训分享Java常见排序算法之插入排序

上面就是插入排序的原理。

2.2、插入排序和选择排序的区别

比如就上面这个例子而言,插入排序是将0从索引为4的位置移动到索引3、2、1、0,最终才算结束。而选择排序是找到最小的值0,直接跟1进行交换,0到1的位置,1到0的位置。大家可以翻看前面关于选择排序的介绍。

三、插入排序的代码实现

以下是java代码的实现:

/**

* 插入排序

*/

public static void algorithm5(){

//原始数组

int[] array={1,2,3,4,0,5};

//数组的长度

int length=array.length;

//对数组进行遍历 for (int i = 0; i < length; i++) {

//第二个循环仅仅是将当前数据跟自己左边的数字进行比较,如果小于左边数字则交换位置,否则位置不变。

for (int j = i; j > 0 && array[j]<array[j-1]; j--) {

int temp = 0;

temp = array[j-1];

array[j-1]=array[j];

array[j]=temp;

}

}

//将排好序的数组打印输出

for (int i = 0; i < length; i++) {

System.out.print(array[i]+",");

}

}

以上是插入排序的java代码实现,代码中的第二个for循环是重点,第二个for循环是只比较当前数据左边的值,如果比左边的值小则交换位置,否则位置不变。

3.1 插入排序的时间复杂度

插入排序的时间复杂度有两种:

1、当数组本身是有序的,比如{1,2,3,4,5},则采用插入排序的时间复杂度是O(n)。原因:如果数组本身是有序,插入排序需要每两个挨着的数字进行比较一次,总共比较N-1次,所以时间复杂度是O(n)。

2、当数组是无序的,最坏的情况下需要比较(n^2)/2次,所以时间复杂度是O(n^2)。

四、总结

根据插入排序的时间复杂度来看,插入排序适合如下类型的数组:

1、数组中的每一个元素距离其最终的位置都不远。比如{1,0,2,3,4,5},这个数组中0最终位置应该是头1个位置,0此时的位置距离1位置不远。

2、一个有序的大数组中融入一个小数组。比如有序大数组{1,2,3,4,5,6},融入一个小数组{0,1}。

3、数组中只有几个元素的位置不正确。

上述这三种情况的数组适合使用插入排序算法。打过麻 将的同学想想,打麻 将过程中不停地摸牌、打 牌、整理牌的过程是不是就是一次插入排序呢!

排序是算法的基础,排序的用途很多。看完本节内容之后,大家不妨自己动手写个代码将无需的扑 克 牌进行排序,看更适合哪种排序算法。

向AI问一下细节

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

AI