javaScript实现归并排序
归并排序是一个O(nlogn)的算法,其基本思想就是一个分治的策略,先进行划分,然后再进行合并,下面举个例子。有这样一组数据:
[5,4,1,22,12,32,45,21]
如果对它进行归并排序的话,首先将它从中间分开,这样,它就被分成了两个数组:
[5,4,1,22]与 [12,32,45,21]
对这两个数组,也分别进行这样的操作,逐步的划分,直到不能再划分为止(每个子数组只剩下一个元素),这样,划分的过程就结束了。
接下来,我们进行归并操作,划分过程是从上到下进行的,而归并的过程是从下往上进行的,最下层[5],[4]这两个数组,如果按升序排列,将他们合并后的数组就是[4,5]。[1],[22]这两个子数组合并后是[1,22]。而[4,5]与[1,22],这两个数组同属一个分支,他们也需要进行合并,由于这两个子数组本身就是有序的,所以合并的过程就是,每次从待合并的两个子数组中选取一个最小的元素,然后把这个元素放到合并后的数组中,前面两个数组合并后就是[1,4,5,22]。依次类推,直到合并到最上层结束,这是数据的排序已经完成了。
归并的过程是从下往上的。
它是一个在效率上高于一般排序的算法.一般排序:冒泡, 插入, 选择排序的时间复杂度为O(n^2), 而归并排序的时间复杂度为O(nlogn),如果N(及排序项的数目)是10000.那么 n^2 就是100000000, 而 nlogn 则是40000. 也就是如果这个数量的数据.如果用归并排序需要40s的时间,那么用插入排序则需要28个小时.
归并排序算法的核心:核心思想就是分治算法.先进行划分,再进行排序归并.归并两个有序的数组.即归并两个有序的数组A和B,然后就有了包含这两个新数组的数组C.
即一次拿出A和B的数组项进行比较.小的就插入到新容器C中.直到一方已经插入完毕.如果另一方还有剩余那么就表示剩余的是有序的而且比较大的.那么就直接连接到C数组容易的后面即可.
/* 排序并合并*/ function merge(left, right) { var res = []; while(left.length > 0 && right.length > 0) { if(left[0] < right[0]) { res.push(left.shift()); } else { res.push(right.shift()); } } /* 当左右数组长度不等.将比较完后剩下的数组项链接起来即可 */ return res.concat(left).concat(right); } function mergeSort(arr) { if(array.length == 1) { return arr }; /* 首先将无序数组划分为两个数组 */ var mid = Math.floor(array.length / 2); var left = array.slice(0, mid); var right = array.slice(mid); /* 递归分别对左右两部分数组进行排序合并 */ return merge(mergeSort(left), mergeSort(right)); } var arr = [23, 47 ,81 ,95 ,7, 14, 39, 55, 62, 74] console.log(mergeSort(arr));
相关文章
- javascript 高级教程 视频_精通JavaScript
- JavaScript小技能:事件
- 【说站】javascript Array.sort()的数组排序
- JavaScript刷LeetCode之-双指针技巧(上)
- 用javascript分类刷leetcode-排序算法(图文视频讲解)
- 在JavaScript中使用最大优先队列 - wuuconix's blog
- JS引擎(1):JS引擎擂台赛,JavaScript引擎的特征比较及术语科普
- JavaScript 编码指南详解编程语言
- JavaScript学习总结(九)——Javascript面向(基于)对象编程详解编程语言
- JavaScript:九种弹出对话框详解编程语言
- 在Javascript中为String对象添加trim,ltrim,rtrim方法
- 从JavaScript的函数重名看其初始化方式
- Javascript常用运算符(Operators)-javascript基础教程
- javascript贪吃蛇实现代码
- 一个特殊的排序需求的javascript实现代码
- javascript实现滚动效果代码整理
- JavaScript随机排序(随即出牌)
- javascript节点排序实现代码
- javascript快速排序函数代码
- JavaScript实现快速排序(自已编写)
- Javascript图像处理—亮度对比度应用案例
- javascript对select标签的控制(option选项/select)
- javascript-表格排序(降序/反序)实现介绍(附图)
- Javascript自定义排序node运行实例
- html+javascript实现可拖动可提交的弹出层对话框效果
- JavaScript数值数组排序示例分享
- 什么是MEAN?JavaScript编程中的MEAN是什么意思?
- JavaScript中伪协议javascript:使用探讨
- javascript实现表格排序编辑拖拽缩放
- javascript使用数组的push方法完成快速排序