首页 / 软件开发 / 数据结构与算法 / 浅谈算法和数据结构 三 合并排序

浅谈算法和数据结构 三 合并排序2015-02-27合并排序，顾名思义，就是通过将两个有序的序列合并为一个大的有序的序列的方式来实现排序。合并排序是一种典型的分治算法：首先将序列分为两部分，然后对每一部分进行循环递归的排序，然后逐个将结果进行合并。

合并排序最大的优点是它的时间复杂度为O（nlgn），这个是我们之前的选择排序和插入排序所达不到的。他还是一种稳定性排序，也就是相等的元素在序列中的相对位置在排序前后不会发生变化。他的唯一缺点是，需要利用额外的N的空间来进行排序。

一 原理

合并排序依赖于合并操作，即将两个已经排序的序列合并成一个序列，具体的过程如下：

申请空间，使其大小为两个已经排序序列之和，然后将待排序数组复制到该数组中。

设定两个指针，最初位置分别为两个已经排序序列的起始位置

比较复制数组中两个指针所指向的元素，选择相对小的元素放入到原始待排序数组中，并移动指针到下一位置

重复步骤3直到某一指针达到序列尾

将另一序列剩下的所有元素直接复制到原始数组末尾

该过程实现如下，注释比较清楚：

private static void Merge（T[] array, int lo, int mid, int hi）{int i = lo, j = mid + 1;//把元素拷贝到辅助数组中for （int k = lo; k <= hi; k++）{aux[k] = array[k];}//然后按照规则将数据从辅助数组中拷贝回原始的array中for （int k = lo; k <= hi; k++）{//如果左边元素没了， 直接将右边的剩余元素都合并到到原数组中if （i > mid）{array[k] = aux[j++];}//如果右边元素没有了，直接将所有左边剩余元素都合并到原数组中else if （j > hi）{array[k] = aux[i++];}//如果左边右边小，则将左边的元素拷贝到原数组中else if （aux[i].CompareTo（aux[j]） < 0）{array[k] = aux[i++];}else{array[k] = aux[j++];}}}

下图是使用以上方法将ＥＥＧＭＲ和ＡＣＥＲＴ这两个有序序列合并为一个大的序列的过程演示：