找回密码
 立即注册
  • QQ空间
  • 回复
  • 收藏

算法之归并排序

admin 2019-3-13 22:35 139人围观 C++相关

排序是算法中最基本的题目,其中很重要的一个排序算法就是归并排序,也叫合并排序。归并排序是算法里典型的策略中分治策略的最基本的一个实现,也是很多算法类书籍讲解算法的时候最喜欢作为引导的一个题目。归并排序总是被拿来作为算法书的开篇主要是由于下面的几个特点:

面试中总被问起的算法排序题目;

非常典型的分治策略的算法题目;

非常适合算法复杂度分析的练手题目;


今天我们就来看看归并排序是怎么回事,以及在JavaScript中的实现。

引导


先定义一下我们的题目,题目是:

给定数组,设计算法给数组进行排序;

输入: 任意乱序的数组;

输出: 从小到大顺序的数组。


解决思路


分治策略的核心就是分和治,简单的说就是,大的问题逐个分解,然后解决分解后的小问题。最后合并解决完的小问题,即大的问题即被解决。
就归并排序来讲,就是把输入的数组(大问题)逐个分解为小的问题(小数组),然后解决小问题(对小问题进行排序),最后把合并解决完后的小问题(合并排序后的数组),这样就得到了我们需要的排序后的问题。
下面,我们用一个数组来做为例子:
第一步:数组 [5, 4, 1, 8, 7, 2, 6, 3]
第二步:数组分解为两个数组 [5, 4, 1, 8]和[7, 2, 6, 3]
第三步:递归调用自身逐个分解并合并排序
第四步:数组[1, 4, 5, 8]和[2, 3, 6, 7]
第五步:合并后得到[1, 2, 3, 4, 5, 6, 7, 8]

伪代码


代码部分也分两步来,第一步解决排序,第二步解决合并,如下:
    // 输入: n长度的乱序数组A// 输出: n长度的顺序数组A// ===================函数mergeSort,输入A如果数组长度为1或者0,直接返回;否则,继续:B = 递归调用mergeSort函数,排序数组A的前n/2;C = 递归调用mergeSort函数,排序数组A的后n/2;调用合并merge函数,返回merge(B, C);

    第二部分:合并子问题
      // 输入: 两个顺序的数组B合C(n/2长度)// 输出: 顺序的数组Di = j = 0;for k=0 to n-1if B[i] > C[j] D[k] = C[j], j++else D[k] = B[i], i++
      第二部分这里需要考虑的是如果数组长度不一样的话,C或者D的数组某一个数组的元素取完后的情况的处理。读者可以自己思考一下。

      归并排序之js实现


      下面我们用js来实现归并排序,如下:
        functionmergeSort(arr) { var l = arr.length, i = Math.floor(l / 2);if (l === 1 || l === 0) {return arr; } else {return doMerge(mergeSort(arr.slice(0, i)), mergeSort(arr.slice(i, l))); }}
        functiondoMerge(aArr, bArr) {var al = aArr.length, bl = bArr.length, k = al + bl, res = [], j = l = 0;for (i = 0; i < k; i++) {if (l >= bl || aArr[j] < bArr[l]) { res[i] = aArr[j]; j++; } else { res[i] = bArr[l]; l++; } }
        return res;
        }

        算法复杂度


        这里简单介绍下归并排序的算法复杂度。算法复杂度通常用大O的表示法,并且忽略常数和低阶多项式,只保留最高阶表达式。例如,我们的归并排序的复杂度为O(nlogn)。
        复杂度分析,不知道O(nlogn)的来源的,大家可以用树形分析法,简单的讲数组每一次递归需要执行的操作列出来,然后画成树形结构,你就会得到nlogn的多项式了。这样保留最高向即是O(nlogn)。

        ----------------------------------------------------------------------------------------------------------------------
        我们尊重原创,也注重分享,文章来源于微信公众号:frontThink,建议关注公众号查看原文。如若侵权请联系qter@qter.org。
        ----------------------------------------------------------------------------------------------------------------------

        鲜花

        握手

        雷人

        路过

        鸡蛋

        yafeilinux和他的朋友们微信公众号二维码

        微信公众号

        专注于Qt嵌入式Linux开发等。扫一扫立即关注。

        Qt开源社区官方QQ群二维码

        QQ交流群

        欢迎加入QQ群大家庭,一起讨论学习!

        我有话说......