流年似水博客开通了,本站主要是写关于Web和大数据方面内容,正在更新中,欢迎大家光临!
  1. 文章:97 篇
  2. 总浏览:63,334 次
  3. 评论:22条
  4. 最后更新:2020-06-08
  5. 分类目录:39 个

js数据结构与算法-归并排序

算法 l, xy 679℃ 1评论


1 前言

js数据结构与算法 系列用的语言是javascript , 初衷在于入门数据结构与算法和方便以后复习。

这篇文章主要讲述归并排序的一些例子、复杂度分析、动画、还有算法可视化工具。

2 归并排序思想介绍

2.1 原理:

排序一个数组,先将数组均分成两份的方式拆分为最小份,每份剩一个值,再将份进行比较,按照大小合并至一个数组。

2.2 运行过程分为两步:

  • 自上而下的递归
  • 自下而上的迭代

2.3 递归拆分数组:

1.先将数组拆分通过floor(n/2)的方式拆分为arr1和arr2两个数组
2.如果长度大于4,再继续将arr1按照floor(n/2)的方式拆分为arr11和arr12,arr2相同
3.按照第(2)部方式一直拆,也就需要写个方法,来一直执行这个函数,直到最后只剩下一个数据停止递归

2.4 迭代法将数组合并:

1.定义一个空数组result,再定义两个指针分别指向arr1和arr2的起始位置
2.比较两个指针所指向数值的大小,将较大的一个存入数组result,此时存在较大值的指针向右侧移动,继续比较
3.循环(2)步骤,将一开始拆分的一组1个值按照顺序合并到result

举个小例子:迭代法将数组合并时的比较,相当于两队人马的擂台比武,两队分别为A队和B队,A队和B队各上场一人比武,A队的输了,换A队的下一个人上场再和B队的这个人的比,就这样一直比,就会排出每个人的名次。

3 javascript实现归并排序:

3.1 第一步:递归来实现拆分元素

 function mergingSort(arr) {
      let len = arr.length;
      if (len < 2) return arr;

      let mid = len >> 1; // len>>1,相当于Math.floor(len/2);
      let arr1 = arr.slice(0, mid);
      let arr2 = arr.slice(mid);
      return merge(mergingSort(arr1), mergingSort(arr2))
 }

 let tag = 1;
 function merge(arr1, arr2) {
     console.log("tag" + tag + "=", arr1, arr2);
     tag++;
 }

执行结果:

拆分成功,这个方法将数组拆分成单个数组

3.2 第二步:迭代方法排序数组并合并

function mergingSort(arr) {
            let len = arr.length;
            if (len < 2) return arr;
            let mid = len >> 1; // len>>1,相当于Math.floor(len/2);
            let arr1 = arr.slice(0, mid);
            let arr2 = arr.slice(mid);
            
            console.log("mid-------", mid, arr1, arr2)
            return merge(mergingSort(arr1), mergingSort(arr2))
        }

        let tag = 1;
        function merge(arr1, arr2) {

            console.log("tag" + tag + "=", arr1, arr2);
            tag++;

            let result = [];
            while (arr1.length && arr2.length) { //选取两个序列中的较小值放入新数组
                if (arr1[0] <= arr2[0]) {
                    result.push(arr1.shift()) 
                } else {
                    result.push(arr2.shift()) 
                }
            }
            while (arr1.length > 0) { //序列1中多余的元素移入新数组
                result.push(arr1.shift())
            }
            while (arr2.length) { //序列2中多余的元素移入新数组
                result.push(arr2.shift())
            }

            console.log("return merge----------", result)

            return result;
        }
       
      mergingSort([3, 2, 4, 5, 1]);

执行结果及执行过程:

解:拦截了middle截取值的结果,merge方法传入值tag和每次merge方法运行返回值return merge,运行规律总结为:

  • 先拆分2份,将第一份拆解完成,再拆解第二份,以此类推
  • 拆到只剩一个值时运行merge函数根据大小合并
  • 两两合并完再合并4个,直到全部合并完

3.3 动画效果描述过程:

4 归并排序时间复杂度、空间复杂度、稳定性

复杂度分析是整个算法学习的精髓。

  • 时间复杂度: 一个算法执行所耗费的时间。
  • 空间复杂度: 运行完一个程序所需内存的大小。

我们除了学习算法原理和实现之外,更重要的是学会如何评价、分析一个排序算法。

4.1 执行效率

从效率上看,归并排序可算是排序算法中的佼佼者。假设数组长度为 n,那么拆分数组共需 logn 步,又每步都是一个普通的合并子数组的过程,时间复杂度为 O(n),故其综合时间复杂度为 O(n log n)。

最佳情况:T(n) = O(n log n)。
最差情况:T(n) = O(n log n)。
平均情况:T(n) = O(n log n)。

4.2 内存消耗

这是因为归并排序的合并函数,在合并两个有序数组为一个有序数组时,需要借助额外的存储空间。

实际上,尽管每次合并操作都需要申请额外的内存空间,但在合并完成之后,临时开辟的内存空间就被释放掉了。在任意时刻,CPU 只会有一个函数在执行,也就只会有一个临时的内存空间在使用。临时内存空间最大也不会超过 n 个数据的大小,所以空间复杂度是 O(n)。
所以,归并排序不是原地排序算法。

4.3 稳定性

merge 方法里面的 left[0] <= right[0] ,保证了值相同的元素,在合并前后的先后顺序不变。归并排序是稳定的排序方法。

 

转载请注明:流年似水 » js数据结构与算法-归并排序

喜欢 (0)or分享 (0)

Warning: copy(https://cn.gravatar.com/avatar/?s=54&d=%2Fwp-content%2Fthemes%2Fyusi1.0%2Fimg%2Fdefault.png&r=g): failed to open stream: HTTP request failed! HTTP/1.1 400 Bad Request in /usr/share/nginx/html/timewentby/wp-content/themes/yusi1.0/functions.php on line 239

Warning: copy(/wp-content/themes/yusi1.0/img/default.png): failed to open stream: No such file or directory in /usr/share/nginx/html/timewentby/wp-content/themes/yusi1.0/functions.php on line 243
发表我的评论
取消评论

表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址
(1)个小伙伴在吐槽

  1. Warning: copy(https://cn.gravatar.com/avatar/92de644add16aea9a83dd15bea501268?s=54&d=%2Fwp-content%2Fthemes%2Fyusi1.0%2Fimg%2Fdefault.png&r=g): failed to open stream: HTTP request failed! HTTP/1.1 400 Bad Request in /usr/share/nginx/html/timewentby/wp-content/themes/yusi1.0/functions.php on line 239
    学到了,?
    花花2019-11-05 15:31 Reply