算法之归并排序

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

面试中总被问起的算法排序题目；非常典型的分治策略的算法题目；非常适合算法复杂度分析的练手题目；其它。

今天我们就来看看归并排序是怎么回事，以及在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长度)
// 输出： 顺序的数组D
i = j = 0;
for k=0 to n-1
if B[i] > C[j]
   D[k] = C[j], j++
else 
  D[k] = B[i], i++

第二部分这里需要考虑的是如果数组长度不一样的话，C或者D的数组某一个数组的元素取完后的情况的处理。读者可以自己思考一下。

归并排序之js实现

下面我们用js来实现归并排序，如下：

/*
 * 归并排序
 */
function mergeSort(arr) {
    var n = arr.length, index = Math.floor(n/2), leftArr, rightArr;
    if (arr.length === 0 || arr.length === 1) {
        return arr;
    }
    leftArr = mergeSort(arr.slice(0, index));
    rightArr = mergeSort(arr.slice(index, n));
    return merge(leftArr,  rightArr);
}

/*
 * 合并过程
 */
function merge (arrLeft, arrRight) {
    var k = i = j = 0, ll = arrLeft.length, lr = arrRight.length, nl = ll + lr, res = [];
    while (i < ll && j < lr) {
        if (arrLeft[i] > arrRight[j]){
            res[k++] = arrRight[j++];
        } else {
            res[k++] = arrLeft[i++];
        }
    }
    if (i >= ll) {
        while (k < nl) {
            res[k++] = arrRight[j++];
        }
    } else  if (j >= lr) {
        while (k < nl) {
            res[k++] = arrLeft[i++];
        }
    }

    return res;
}

算法复杂度

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

front-thinking / blogs