前端排序算法 - 归并排序算法 (1)
2023-09-11 14:22:18 时间
归并排序(MERGE-SORT)是利用归并的思想实现的排序方法,该算法采用经典的分治(divide-and-conquer)策略,
分(divide)成一些小的问题然后递归求解,
而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起。
代码演示gif:
归并排序算法我们采用递归的方法 先将数组一直进行折半拆分 拆到长度为一的数组 再两两合并
比如: [5, 6, 3, 1, 8, 7, 2, 4]
1. 先将数组一直进行折半拆分 拆到长度为一的数组 比如 [ 5 ] [ 6 ] [ 3 ] [ 1 ] 2. 再拆分的个体进行两两合并 用 merge 方法 得到 [ 5, 6 ] 和 [ 1, 3 ] 再将这两个数组进行合并 得到 [1, 3 , 5, 6] 这个时候左边合并完成 进行右边拆分合并 [ 8 ] [ 7 ] 和 [ 2 ] [ 4 ] 得到 [2, 4 , 7 , 8 ] 所以我们这个时候得到两个数组 [1, 3 , 5, 6] 和 [2, 4 , 7 , 8 ] 对这两个数组进行合并 得到最后结果 1,2,3,4,5,6,7,8
白话思路:
先拆分 再合并
先拆分左边的 拆分到个体为1 的数组再进行两两合并 得到最终结果
接着对右边进行同样操作
得到最终结果
这个时候左边和右边都得到长度为 n/ 2 的排序好的数组了
最后一步 将左右两边进行merge 重新排序
js 的代码实现 归并排序算法:
let data = [5, 6, 3, 1, 8, 7, 2, 4] console.log(mergeSort(data)) function mergeSort (arr) { var len = arr.length; if(len < 2) { return arr; } let middle = Math.floor(len/2); let left = arr.slice(0, middle) let right = arr.slice(middle) return merge(mergeSort(left), mergeSort(right)) } function merge(left, right) { let result = [] while (left.length> 0 && right.length> 0) { if (left[0] <= right[0]) { result.push(left.shift()) } else { result.push(right.shift()) } } while(left.length) result.push(left.shift()) while(right.length) result.push(right.shift()) return result; }
git 地址: https://gitee.com/guangzhou110/front-end-sorting-algorithm
相关文章
- 野生前端的数据结构练习(11)动态规划算法
- Java实现 蓝桥杯VIP 算法提高 邮票面值设计
- Java实现 蓝桥杯VIP 算法训练 s01串
- (算法)成都麻将
- Atitit 前端算法技术体系总结 目录 1. 3. Ui方面的算法 32 3.1. 软键盘算法 计算软键盘上下左右按键位置 32 3.2. Sprire生成随机位置算法 随机数算法 3
- Atitit 机器学习算法分类 五大分类v5 t56.docx Atitit 机器学习算法分类 目录 1. 传统的机器学习算法 vs 深度学习1 1.1. 传统的机器学习算法包括决策树、聚类、贝
- 【抽水蓄能电站】基于粒子群优化算法的抽水蓄能电站的最佳调度方案研究(Matlab代码实现)
- 基于人工鱼群优化的电网规划算法matlab仿真
- 智能优化算法应用:基于灰狼算法的Otsu图像多阈值分割-附代码
- 智能优化算法:沙猫群算法—附代码
- Python实现哈里斯鹰优化算法(HHO)优化循环神经网络分类模型(LSTM分类算法)项目实战
- 单词子集-c语言解决-暴力算法和字符串最大值数判断算法
- C语言之——CRC-64算法
- 数据结构和算法参考网址