简易的网站建设,网站联系我们 怎么做地图,宁波市内做公司网站的公司,怎么看网站开发的好坏一、概述
排序是算法中的一部分。所以我们学习排序也是算法的入门#xff0c;为了能让大家感受到排序是算法的一部分#xff0c;我举个例子证明一下#xff1a;比如麻将游戏#xff0c;发完牌之后需要对手上的牌进行排序#xff0c;大家想想#xff0c;麻将排序如何排呢…一、概述
排序是算法中的一部分。所以我们学习排序也是算法的入门为了能让大家感受到排序是算法的一部分我举个例子证明一下比如麻将游戏发完牌之后需要对手上的牌进行排序大家想想麻将排序如何排呢它有什么特点呢而且在摸牌打牌的过程中我们要不断的排序如何排序呢选择什么排序算法最快呢
以上这种情况我们就可以分析选择哪种排序算法更高效。比如下图已经有一副固定顺序的牌了 此时轮到我们摸牌摸到的牌如下 此时要将这个“三同”放到上面的一副牌中就存在如下规律
1、正常“3同”应该放到“2同”和”4同“中间。
2、跟其他花色的牌没有关系甚至跟”5同“也没有关系。只需要把”3同“放到”2同“和”4同“中间就行。至于”2同”和”4同”在哪里不要紧。
我们前面学习了选择排序如果使用选择排序对上面这副牌进行排序是否合适呢显然是不合适的因为选择排序必须从“七万”开始比较选择最小牌跟第一张牌交换位置依次类推。但是此处麻将牌的“3同”跟”七万“没有关系不需要影响”7万“。所以使用选择排序不合适因为时间负责度很高此处使用插入排序会更好什么是插入排序呢就是本节需要介绍的内容。
二、插入排序
插入排序属于简单排序的一种通常指的简单排序只是因为其算法思路比较容易理解不代表其用途很简单。为了让大家掌握插入排序我们先看看插入排序的原理。
2.1、插入排序的原理
首先有一个待排序的数组如下 以上数组中只有一个数字0的顺序需要排列其他数字的顺序都是对的。这种数组使用插入排序的效率更高下面介绍此数组使用插入排序的流程。
1、先比较1和2如果2比1小则交换位置。否则不交换位置。此数组不需要交换位置。 2、再比较2和3如果3比2小则交换位置。但是实际3比2大所以不交换位置保持不变。 3、同理3和4比较也不需要交换位置保持不变 4、接来下4和0比较0小于4所以交换位置 交换位置之后的数组如下 5、因为3的邻居发生变化所以3和0再次比较0比3小交换位置交换之后的数组如下 6、依次类推0分别和2交换位置之后的数组如下 0再和1交换位置的数组如下 这样一个数组的顺序就对了但是循环还没有完成因为我们刚才仅仅循环到数字4这个位置数字5还没有比较。
7、最后比较4和5如果5比4小则交换位置但是5比4大所以位置不变。数组循环完毕最终排序如下 上面就是插入排序的原理。
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 lengtharray.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、当数组本身是有序的比如{12345}则采用插入排序的时间复杂度是O(n)。原因如果数组本身是有序插入排序需要每两个挨着的数字进行比较一次总共比较N-1次所以时间复杂度是O(n)。
2、当数组是无序的最坏的情况下需要比较(n^2)/2次所以时间复杂度是O(n^2)。
四、总结
根据插入排序的时间复杂度来看插入排序适合如下类型的数组
1、数组中的每一个元素距离其最终的位置都不远。比如{1,0,2,3,4,5}这个数组中0最终位置应该是第一个位置0此时的位置距离第一个位置不远。
2、一个有序的大数组中融入一个小数组。比如有序大数组{1,2,3,4,5,6}融入一个小数组{0,1}。
3、数组中只有几个元素的位置不正确。
上述这三种情况的数组适合使用插入排序算法。打过麻将的同学想想打麻将过程中不停地摸牌、打牌、整理牌的过程是不是就是一次插入排序呢
排序是算法的基础排序的用途很多。看完本节内容之后大家不妨自己动手写个代码将无需的扑克牌进行排序看更适合哪种排序算法。
