若人们不相信数学简单,只因他们未意识到生命之复杂。
—— 约翰·冯·诺伊曼
归并排序简介
归并排序(Merge Sort),是创建在归并操作上的一种有效的排序算法。1945年由约翰·冯·诺伊曼首次提出。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用,且各层分治递归可以同时进行。
归并操作
归并操作(merge),也叫归并算法,是指将两个已经排序的序列合并成一个序列的操作。
归并操作有两种方法可实现:迭代法和递归法。本篇主要介绍性能最优的迭代法。
归并排序思想
假设初始序列含有n个记录,则可以看成n个有序的子序列,每个子序列的长度为1,然后两两归并,得到$\lceil n/2 \rceil$($\lceil x \rceil$表示不小于x的最小整数)个长度为2或1的有序子序列;再两两归并,···,如此重复,直至得到一个长度为n的有序序列为止,这种排序方法称为2路归并排序。
归并排序过程
具体过程示意图:
算法实现
1 | /** |
输出结果:1
2
3
4
5
6
7
8
9
101000
10
20
30
40
50
60
70
80
90
算法分析
时间复杂度
对于递归法,总的时间复杂度为$\Theta(n\log n)$,而且是其最好、最坏、平均的时间性能。
对于迭代法,其最优时间复杂度为$\Theta(n)$。
空间复杂度
对于递归法,其空间复杂度为$\Theta(n + \log n)$。
对于迭代法,其空间复杂度为$\Theta(n)$。
稳定性
归并排序是一种稳定的排序方法。