排序:(五)归并排序

一、特点

Merge sort is an O(nlgn) comparison-based sorting algorithm. Most implementations produce a stable sort. It is a divide and conquer algorithm.

二、 算法

Conceptually, a merge sort works as follows:

  1. If the list is of length 0 or 1, then it is already sorted. Otherwise:
  2. Divide the unsorted list into two sublists of about half the size;
  3. Sort each sublist recusively(递归地) by re-applying the merge sort;
  4. Merge the two sublists back into one sorted list;

三、性能

1. 时间性

性质1: 对任何包含N个元素的文件进行排序,归并排序需要执行大约NlgN次比较操作。

2. 空间性

性质2: 归并排序使用与N成正比的额外内存空间。

性质3: 归并排序所需资源与输入初始顺序无关。

三、快速排序与归并排序比较

归并排序是以 比较 为基础的,而快速排序是以 选择 为基础的。

快速排序包括一个选择的过程,后面跟两个递归调用。 而归并排序相反,它是把两个排好序的文件组合成一个较大的有序文件。 归并的执行过程是两个递归调用之后是一个归并过程。

快速排序更适合称为 分治算法 :在一个递归实现中,大部分工作是在递归调用之前完成的。 而递归归并排序的本质是 分治法 :首先问题被分成两部分;然后分别解决每一部分。 归并排序处理第一个问题是一个小问题;结束时处理最大的子文件。 快速排序从处理最大的子文件开始,以处理最小的子文件结束。

很多好算法都使用分治算法和树结构。

四、总结

归并排序是一种稳定的排序方法,这一特性对于某些稳定性要求高的应用是可选的方法。 而快速排序和堆排序都不是稳定的方法。

归并的另一个重要特性是它可以顺序访问数据。这在一些高性能计算机上有优势,因为在这些环境中顺序访问数据更快。

归并排序的缺点是算法实现的过程中,所需的空间和N成正比。

归并排序并不比堆排序编码要困难,且它的内部循环的长度介于快速排序和堆排序的内部循环之间, 因而如果速度不是主要问题,它也没有最坏情况下的性能,还有足够空间可以使用,归并排序是值得考虑的。

五、扩展

1. 基本算法的改进

如快速排序所讨论的,可以通过对小文件处理来改进大多数递归算法。 因此,像快速排序所做的那样,对小文件使用插入排序可以改进算法效率达10%至15%。

第二种改进是消除归并时把元素复制到辅助数组所花费的时间。 可以使用两个数组轮换调用。

2. 自底向上的非递归实现

这种方法有些类似希尔排序。希尔排序是对每隔n个元素的序列合并,这种自底向上的方法是先对相邻的每2个元素排序,再对相邻的每4个元素排序,再对相邻的每8个元素排序,以此类推。

发表评论