原文链接:Computer Algorithms: Merge Sort

简介

一般来说,排序算法主要被分为两类--基于比较的算法和基于非比较的算法。我已经发了一些关于前一类算法的帖子。插入排序,冒泡排序和希尔排序是基于比较模型的。这三个算法的问题是他们的复杂度都是O(n^2),所以他们非常慢。

那么有没有比O(n^2)更快的排序列表的方法呢?答案是有的,下面就让我们看看这么一个算法。

之前提到的三个算法(插入,冒泡和希尔)的共同特点是我们是从原始列表里两两元素取出,然后进行比较的。

插入排序和冒泡排序使用了太多的比较,这也是归并排序需要克服的地方

插入排序和冒泡排序使用了太多的比较,这也是归并排序需要克服的地方

在原始列表里进行比较不是最好的方式而且我们也不需要那么做。作为替代,我们可以尝试将列表分成更小的子列表然后排序他们。在排序完更小的子列表以后(这么做要比直接排序整个原始列表要简单),我们可以尝试将小的子列表合并成一个有序列表。这个技术就是典型的“分治”法(分而治之)。

一般来说,如果一个问题太难以至于无从下手,我们可以尝试将它分成更小的子问题,然后尝试解决这些子问题。然后我们可以将子问题的结果合并起来(从而解决原始问题)。

如果排序大列表太困难,我们可以将它分割成更小的子列表,然后排序他们

如果排序大列表太困难,我们可以将它分割成更小的子列表,然后排序他们

综述

归并排序是一个基于分治法的比较排序算法。目前看来还不错,那么当我们有一个非常大的列表需要排序。显然,如果我们将列表分成两个子列表,然后排序他们会更好些。如果等分以后还是太大,我们就继续分割,直到我们得到可以很简单地排序为止(正如下图所示)。

归并排序是一个分治法的范例

合并排序过的子列表

上图描述了在算法的某些步骤中,我们已经得到两个排序的列表而巧妙的地方是合并它们。然而,这也不是特别难。 我们可以比较两个列表的第一个元素,将其中较小的元素取出放在一个新的列表中(这样得到的列表一定是有序的列表)。

实现

好消息是这个算法不但快速而且实现起来也不难,站一个开发者角度上,这实在是太美妙了。下面是PHP版的实现。注意:每一个遵从分治法的算法都可以使用递归方案轻易实现。然而,因为递归的性能很糟,所以你可能需要找到一个迭代的方式。一般的,递归可以被花费额外内存空间的迭代方式取代。下面是一个递归版的归并排序。

$input = array(6, 5, 3, 1, 8, 7, 2, 4);

function merge_sort($arr)  
{  
    if (count($arr) <= 1) {
        return $arr;  
    }

    $left = array_slice($arr, 0, (int)(count($arr)/2));  
    $right = array_slice($arr, (int)(count($arr)/2));  

    $left = merge_sort($left);  
    $right = merge_sort($right);  

    $output = merge($left, $right);  

    return $output;  
}  


function merge($left, $right)  
{  
    $result = array();  

    while (count($left) > 0 && count($right) > 0) {  
        if ($left[0] <= $right[0]) {  
            array_push($result, array_shift($left));  
        } else {  
            array_push($result, array_shift($right));  
        }  
    }  

    array_splice($result, count($result), 0, $left);  
    array_splice($result, count($result), 0, $right);  

    return $result;  
}  

// 1, 2, 3, 4, 5, 6, 7, 8
$output = merge_sort($input);

复杂度

归并排序的复杂度是非常棒的,即使在最差情况下他的复杂也是O(n*log(n))。值得注意的是:即便是快速排序的复杂度也可能在最差情况下达到O(n^2)。所以我们可以确定归并排序无论在什么情况下都非常稳定。

归并排序的复杂度是O(n*log(n))

归并排序即使在最差情况下也是O(n*log(n))

为什么归并排序如此有用的两个理由

1. 快捷和稳定

归并排序是一个非常棒的排序算法主要是因为它的快捷和稳定。它的复杂度即使在最差情况下都是O(n*log(n))。注意即使快速排序在最差情况下的复杂度都是O(n^2),当n=20的时候,它比归并要慢4.6倍。

enter image description here

2. 容易实现

另一个理由是归并排序很容易实现。诚然,大多数开发者认为速度快得算法总是难以实现,但是这条守则并不适用与归并排序的情况。

归并排序不那么实用的三个理由

1. 比非比较排序算法慢

归并算法是基于比较模型的,因此它要比在线性时间里排序数据非比较算法要慢。当然,这也由输入数据而定的,所以我们仔细对待输入。

2. 对于初学者来说比较难实现

尽管我不认为这是一个不用归并排序的主要理由,但仍有一些人说它对于初学者来说太难实现了,尤其是合并部分的算法。

3. 在数据基本有序的情况下,它比冒泡和插入排序要慢 再一次提醒,了解输入数据的重要性。如果输入数据基本已经有序,那么插入和冒泡排序会更快。插入和冒泡排序在最好的情况下复杂度是O(n),然而归并排序的最好情况是O(n*log(n))

作为总结,我想说在实践中,归并排序是最好的排序算法质疑,因为它易于实现而且快捷,所以每个开发者都应该牢记它。

相关文章:

  1. Computer Algorithms: Quicksort
  2. Computer Algorithms: Shell Sort
  3. Friday Algorithms: JavaScript Merge Sort