经典排序算法之插入排序

野性酷女 2022-09-12 14:56 188阅读 0赞

### 前言 ###

> 前面我们已经学习了经典排序算法之一的冒泡排序。那么除了经典的冒泡排序还有很多其他的排序算法，今天我们就来学习一个新的排序 - 插入排序。  
> 从名字上看不难理解，其实就是以插入的方式进行排序，在讲数组的插排之前，我们先来看一个生活中比较常见的案例。  
> 相信扑克牌大家应该都不陌生，每当同学小聚或者逢年过节大家也都会玩上几把。那么在玩牌的时候一般都是将洗好的扑克牌放在桌上，然后每个人轮流去抓取。不知道大家是如何管理抓到手中的牌的，我的习惯是将抓在手中的牌按从小到大的顺序排好，当抓到新牌后先跟手里的牌进行比较，然后插入到合适的位置，那么等所有牌抓取完毕后一定是按照从小到大的顺序排列了。其实数组的插入排序就跟我们玩牌非常类似，下面我们就来分析一下

### 插入排序思路分析 ###

> 假设给定一个无序数组nums：\[12,1,8,21,7,4,10\]，现在的需求是用插入排序的方法将数组中的元素进行从小到大排序。
> 
>  *  结合上面玩牌的案例，我们可以假设这个数组就是桌面上洗好的扑克牌，然后我们需要定义一个新的空的数组newNums，用于存放插入的值，可以理解就是我们的手。
>  *  开始抓牌，我们可以把原数组nums中的第一个元素先插入到newNums作为手里的首牌：\[12\]
>  *  然后再取原数组nums中的每一个元素跟新数组newNums中的每个元素比较，将小牌插入到大牌前面。
>  *  这里可以从前往后（从小到大）比也可以从后往前（从大到小）比，看个人喜好，我们的示例中将会采用从后往前比较的方式进行
>  *  由于新数组中的元素都是已经排好序的了，而且最后一个值也肯定是当前数组中最大的，所以在每次进行从后往前比较时如果发现，原数组中取出的值比当前值（新数组正在循环的值）大，则直接插入到当前位置，否则继续向前比较
>     
>      *  用到的知识点：Array.splice(start,deleteCount,insert)，在start位置删除deleteCount个元素，并插入新元素insert。
>      *  start应该是新数组中当前值的索引加1，因为是要插入到当前值后面
>      *  deleteCount取0就是删除0个元素
>      *  insert为原数组中取出的值
>  *  如果在跟新数组中所有的元素都比较完之后，发现都不符合条件，则说明原数组中取出的值应该是新数组中最小的一个，此时应该插在新数组的最前面
>     
>      *  用到的知识点：Array.unshift(num)从数组的开始位置插入一个元素
>  *  外层循环的轮数就是原数组的长度减1，因为第一个值已经被添加到了新数组中
>  *  内层循环则是新数组的长度，因为要跟新数组中的每个值都进行比较

### 插排代码 ###

### 总结 ###

> 本文以我们以日常生活中玩牌的例子引出了我们开发中比较经典排序算法插入排序，并梳理了插入排序的思路及使用到的一些知识点和注意点。最后完成了我们的经典插排算法。  
> 如果喜欢，欢迎点赞，留言加关注哦！！！