算法和数据结构2.5归并排序
2019-07-27 本文已影响0人
数字d
归并排序
归并排序算法会把序列分成长度相等的两个子序列，当无法继续往下分的是时候，也就是序列中只有一个数据时候，就对序列进行归并。
归并指的是把两个排好序的序列合并成一个有序序列。该操作会一直重复，直到所有子序列都归并为一个整体为止。
操作步骤：
排序如下序列
6 4 3 7 5 1 2
先分成两段
6 4 3 7 | 5 1 2
再将子序列分成两段
6 4 | 3 7 | 5 1 | 2
再将序列分成两段
a . 6 4 3 7 5 1 2
b. 6 4 3 7 | 5 1 2
c .6 4 | 3 7 | 5 1 | 2
d .6 4 | 3 7 | 5 1 | 2
f. 6 | 4 | 3 | 7 | 5 | 1 | 2
接下来开始归并，归并块按照分割逆序来归并
如下：f行的6 4 3 7 希望归并到上一行，需要按照d行对数字进行排序，d行的4和6 排序，d行的3和7排序得到如下结果c行的结果
a . 6 4 3 7 5 1 2
b. 6 4 3 7 | 5 1 2
c . 4 6 | 3 7 | 5 1 | 2
d 4 6 | 3 7 | 5 1 | 2
f. 6 | 4 | 3 | 7 | 5 | 1 | 2
接下来对c行按照b行进行归并
a . 6 4 3 7 5 1 2
b. 6 4 3 7 | 5 1 2
c .4 6 | 3 7 | 5 1 | 2
d 4 6 | 3 7 | 5 1 | 2
f. 6 | 4 | 3 | 7 | 5 | 1 | 2
这里单独拿出来说明下，
对4 6 3 7往上一层归并时候，步骤如下：
4 6 | 3 7
只比较模块中第一个数据，小的拿出来做为归并结果
归并结果：[]
待归并数据 ：4 6 | 3 7
因为 3 < 4 第一次归并结果之后：
归并结果 [3]
待归并数据：
4 6 | 7
因为 4 < 7
归并结果 [3 4]
待归并数据：
6 | 7
因为6 < 7
归并结果 [3 4 6]
待归并数据：
7
所以归并结果是[3 4 6 7]
,同样的情况对5 1 2 进行归并
归并结果是
5 1 2 --->
1 2 5
接下来对b行的数据进行归并
a . 6 4 3 7 5 1 2
b 3 4 6 7 1 2 5
b行归并步骤：
归并结果：
待归并数据：
3 4 6 7 | 1 2 5
1 < 3
归并结果：1
待归并数据：
3 4 6 7 | 2 5
2 < 3
归并结果：1 2
待归并数据：
3 4 6 7 | 5
3 < 5
归并结果：1 2 3
待归并数据：
4 6 7 | 5
4 < 5
归并结果：1 2 3 4
待归并数据：
6 7 | 5
5 < 6
归并结果：1 2 3 4 5
待归并数据：
6 7 |
第二模块没有数据了：
归并结果：1 2 3 4 5 6 7
待归并数据：
|
合并完成，序列的排序也就完成了。
时间计算：
归并排序中，分割序列所花费的时间不算在运行时间之内。
在合并两个已经排序好的序列时候，只需要重复比较首尾数据的大小，然后移动较小的数据，因此只需要花费两个子序列长度相应的运行时间。
也就是说完成一行归并所需要的时间取决于这一行的数据量。
无论哪一行都是n个数据，所以每行的运行时间都是O(n).
而将长度为n的序列对半分割直到只有一个数据为止时候，可以分成log2n行，因此，总共有log2n行。也就是说，总的运行时间是O(nlogn)。
