JavaScript 实现 -- 插入排序及优化
2021/6/12 12:21:38
本文主要是介绍JavaScript 实现 -- 插入排序及优化,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
什么是插入排序
先看一下百度百科的定义:
插入排序,一般也被称为直接插入排序。对于少量元素的排序,它是一个有效的算法 [1] 。插入排序是一种最简单的排序方法,它的基本思想是将一个记录插入到已经排好序的有序表中,从而一个新的、记录数增1的有序表。在其实现过程使用双层循环,外层循环对除了第一个元素之外的所有元素,内层循环对当前元素前面有序表进行待插入位置查找,并进行移动。
插入排序的基本思路是,除数组的第一个元素外,对数组中每个元素进行遍历,比较前面元素与当前元素的大小关系,然后将当前元素插入到前面小于(或大于)当前元素的位置,插入排序出如下。
arr = [6,3,2,5,4,1] 数组arr是待排序的数组,首先取出数组中第二个元素 3 ,去比较前一个元素 6 ,3 比 6 小所有把 3 插入到 6 前面,然后取出数组的第三个元素 2 ,去比较前一个元素 6 ,2 比 6 小再比较 6 前面元素 3 ,2 比 3 小所有 2 插入到 3 前面。依次类推,完成整个数组的排序。
插入排序的代码实现
为了方便理解这里先不用两层循环的代码:
Array.prototype.insertionSort = function() { //挂载到原型链上 for (var i = 1; i < arr.length; i++) { //i 表示要插入的元素索引 for(var j = i - 1; j >= 0; j--){ //j 表示要插入元素前一项的索引 if(arr[j] < arr[i]){ //比较当前元素,与前面所以元素 break //前一个元素小于当前元素,找到插入位置,终止本次遍历 } } var temp = arr[i] //存入arr[i]的值 for ( var k = i - 1; k > j; k--){ arr[k + 1] = arr[k] //将所以比arr[i]大的数据向后移 } arr[k + 1] = temp //将arr[i]放到正确位置上 } } var arr = [6,3,2,5,4,1] arr.insertionSort() console.log(arr)
控制台正常输出:
控制台输出的执行过程,以及结果符合预期,说明上面代码没有错误。但上面的代码有三层循环,所有我们再来给它优化一下。
插入排序优化
我们将内层的两个循环优化一下。
Array.prototype.insertionSort = function() { //挂载到原型链上 for (var i = 1; i < arr.length; i++) { var j = i - 1 //j 表示要插入元素前一项的索引 var temp = arr[i] //存入arr[i]的值 while(j >= 0 && arr[j] > temp) { //比较当前元素,与前面所以元素 arr[j+1] = arr[j] //将所以比arr[i]大的数据向后移 j-- } arr[j+1] = temp console.log(arr) } } var arr = [6,3,2,5,4,1] arr.insertionSort() console.log(arr)
控制台输出成功:
插入排序的时间复杂度和稳定性
- 插入排序的时间复杂度是O(n^2);
- 插入排序是稳定的排序算法;
结语
本小节到此结束,谢谢大家的观看!
如有问题欢迎各位指正
记得点赞 + 收藏。
这篇关于JavaScript 实现 -- 插入排序及优化的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 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企业级开发资料新手指南
- 2024-09-26Springboot微服务资料入门教程