排序之插入排序
2022/1/28 23:10:11
本文主要是介绍排序之插入排序,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
文章目录
- 插入排序
- 1 动画
- 2 思想
- 3 解法
- 4 分析
- 时间复杂度
- 空间复杂度
- 稳定性
- 参考资料:
插入排序
1 动画
2 思想
一般人打扑克牌,整理牌的时候,都是按牌的大小(从小到大或者从大到小)整理牌的,那每摸一张新牌,就扫描自己的牌,把新牌插入到相应的位置。
插入排序的工作原理:通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。
3 解法
var insertionSort = function(array) { var len = array.length; if(len <= 1) return; var preIndex, current; for (var i = 1; i < len; i++) { preIndex = i - 1; // 前一个元素的下标 current = array[i]; // 当前元素 while (preIndex >= 0 && current < array[preIndex]) { array[preIndex+1] = array[preIndex]; // 将元素往后挪一位 preIndex--; // 下标前移 } if (preIndex+1 != i) { // 如果相等,证明该数比已排序的序列都大,就不需要进行赋值操作了 array[preIndex+1] = current; // 将当前元素插入到已排序序列中 } } return array; }
4 分析
时间复杂度
-
最佳情况:
O(n)
-
最差情况:
O(n²)
-
平均情况:
O(n²)
空间复杂度
O(1)
稳定性
稳定。
参考资料:
-
JavaScript 数据结构与算法之美 - 十大经典排序算法汇总
-
awesome-coding-js
这篇关于排序之插入排序的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-09-28微服务架构中API版本控制的实践
- 2024-09-28AI给的和自己写的Python代码,都无法改变输入框的内容,替换也不行
- 2024-09-27Sentinel配置限流资料:新手入门教程
- 2024-09-27Sentinel配置限流资料详解
- 2024-09-27Sentinel限流资料:新手入门教程
- 2024-09-26Sentinel限流资料入门详解
- 2024-09-26Springboot框架资料:初学者入门教程
- 2024-09-26Springboot框架资料详解:新手入门教程
- 2024-09-26Springboot企业级开发资料:新手入门指南
- 2024-09-26SpringBoot企业级开发资料新手指南