前端实现插入排序(Insertion Sort),一般也被称为直接插入排序
前端  /  管理员 发布于 8年前   210
插入排序(Insertion Sort),一般也被称为直接插入排序。对于少量元素的排序,它是一个有效、简单的算法
其主要的实现思想是将数据按照一定的顺序一个一个的插入到有序的表中,最终得到的序列就是已经排序好的数据
插入排序的工作方式像许多人排序一手扑克牌,开始时,我们的左手为空并且桌子上的牌面向下
然后,我们每次从桌子上拿走一张牌并将它插入左手中正确的位置,该正确位置需要从右到左将它与已在手中的每张牌进行比较
例如一个无序数组 3、1、7、5、2、4、9、6,将其升序的结果则如下:
一开始有序表中无数据,直接插入3
从第二个数开始,插入一个元素1,然后和有序表中记录3比较,1<3,所以插入到记录 3 的左侧
向有序表插入记录 7 时,同有序表中记录 3 进行比较,3<7,所以插入到记录 3 的右侧
向有序表中插入记录 5 时,同有序表中记录 7 进行比较,5<7,同时 5>3,所以插入到 3 和 7 中间
照此规律,依次将无序表中的记录 4,9 和 6插入到有序表中
将第一待排序序列第一个元素看做一个有序序列,把第二个元素到最后一个元素当成是未排序序列。
从头到尾依次扫描未排序序列,将扫描到的每个元素插入有序序列的适当位置
如果待插入的元素与有序序列中的某个元素相等,则将待插入元素插入到相等元素的后面
用代码表示则如下:
function insertionSort(arr) {
const len = arr.length;
let preIndex, current;
for (let i = 1; i < len; i++) {
preIndex = i - 1;
current = arr[i];
while(preIndex >= 0 && arr[preIndex] > current) {
arr[preIndex+1] = arr[preIndex];
preIndex--;
}
arr[preIndex+1] = current;
}
return arr;
}
在插入排序中,当待排序数组是有序时,是最优的情况,只需当前数跟前一个数比较一下就可以了,这时一共需要比较N- 1
次,时间复杂度为O(n)
最坏的情况是待排序数组是逆序的,此时需要比较次数最多,总次数记为:1+2+3+…+N-1,所以,插入排序最坏情况下的时间复杂度为O(n^2)
通过上面了解,可以看到插入排序是一种稳定的排序方式
插入排序时间复杂度是 O(n2),适用于数据量不大,算法稳定性要求高,且数据局部或整体有序的数列排序
123 在
Clash for Windows作者删库跑路了,github已404中评论 按理说只要你在国内,所有的流量进出都在监控范围内,不管你怎么隐藏也没用,想搞你分..原梓番博客 在
在Laravel框架中使用模型Model分表最简单的方法中评论 好久好久都没看友情链接申请了,今天刚看,已经添加。..博主 在
佛跳墙vpn软件不会用?上不了网?佛跳墙vpn常见问题以及解决办法中评论 @1111老铁这个不行了,可以看看近期评论的其他文章..1111 在
佛跳墙vpn软件不会用?上不了网?佛跳墙vpn常见问题以及解决办法中评论 网站不能打开,博主百忙中能否发个APP下载链接,佛跳墙或极光..路人 在
php中使用hyperf框架调用讯飞星火大模型实现国内版chatgpt功能示例中评论 教程很详细,如果加个前端chatgpt对话页面就完美了..Copyright·© 2019 侯体宗版权所有· 粤ICP备20027696号