《我的第一本算法书》阅读笔记 2-6 归并排序

超、凢脫俗 2022-10-22 05:25 69阅读 0赞

归并排序算法会把序列分成长度相同的两个子序列，当无法继续往下分时（也就是每个子序列中只有一个数据时），就对子序列进行归并。归并指的是把两个排好序的子序列合并成一个有序序列。该操作会一直重复执行，直到所有子序列都归并为一个整体为止。

--------------------

![20210404144442523.png][]

首先，要把序列对半分割。

![20210404144718273.png][]

先分成两段……

![20210404144731210.png][]

再继续往下分……

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70][]

分割完毕。接下来对分割后的元素进行合并。

--------------------

![20210404144829503.png][]

把6和4合并，合并后的顺序为\[4, 6\]。

![20210404144844682.png][]

接下来把3和7合并，合并后的顺序为\[3, 7\]。

![20210404144903211.png][]

下面，我们来看看怎么合并 \[4, 6\]和\[3, 7\]。合并这种含有多个数字的子序列时，要先比较首位数字，再移动较小的数字。

--------------------

![2021040414495641.png][]

由于4＞3，所以移动3。

![20210404145019638.png][]

同样地，再次比较序列中剩下的首位数字。

![20210404145103385.png][]

由于4＜7，所以移动4。

![20210404145128924.png][]

由于6＜7，所以移动6。

![20210404145143343.png][]

最后移动剩下的7。

![20210404145208585.png][]

递归执行上面的操作，直到所有的数字都合为一个整体为止。

--------------------

![20210404145227379.png][]

这里也要比较两个子序列中的首位数字。

![20210404145257338.png][]

由于3＞1，所以移动1。继续操作……

![20210404145310825.png][]

合并完成，序列的排序也就完成了。

--------------------

### 解说 ###

归并排序中，分割序列所花费的时间不算在运行时间内（可以当作序列本来就是分 割好的）。在合并两个已排好序的子序列时，只需重复比较首位数据的大小，然后移动较 小的数据，因此只需花费和两个子序列的长度相应的运行时间。也就是说，完成一行归并所需的运行时间取决于这一行的数据量。

看一下上面的图便能得知，无论哪一行都是 n 个数据，所以每行的运行时间都为 O(n)。 而将长度为 n 的序列对半分割直到只有一个数据为止时，可以分成 ![\\log\_2n][log_2n] 行，因此，总共有![\\log\_2n][log_2n] 行。也就是说，总的**运行时间**为 **O(nlogn)，**这与前面讲到的堆排序相同。

归并排序每次递归需要用到一个辅助表，长度与待排序的表相等，虽然递归次数是O(log2n)，但每次递归都会释放掉所占的辅助空间，所以下次递归的栈空间和辅助空间与这部分释放的空间就不相关了，因而**空间复杂度是O（n）**。

《我的第一本算法书》  \[日\]石田保辉 宫崎修一/著    张贝/译

[20210404144442523.png]: /images/20221022/986d431d0cbd420ab40f5c0a875ad6df.png
[20210404144718273.png]: /images/20221022/f06eaafec2da46a99f5b21595b79d5e2.png
[20210404144731210.png]: /images/20221022/6647e94f02c24870b5c863765b461e58.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70]: /images/20221022/63dc74077cd6476d950c04c337be28a9.png
[20210404144829503.png]: /images/20221022/59db42972a99425ba663771b5e5cc120.png
[20210404144844682.png]: /images/20221022/0007299c619d449e83370e88500e69d7.png
[20210404144903211.png]: /images/20221022/31b32871ead24207acbbab10d65dd085.png
[2021040414495641.png]: /images/20221022/ff38a03334e048b9aa0b68fba548f9fd.png
[20210404145019638.png]: /images/20221022/5ab4cd61311c4a05986b9bb5eeedd4b7.png
[20210404145103385.png]: /images/20221022/dbb491d249fb42e8832f8552b3ed9d48.png
[20210404145128924.png]: /images/20221022/f771cd0521734694966055f034ac73ca.png
[20210404145143343.png]: /images/20221022/61b95accf5984acc961896d38e44390d.png
[20210404145208585.png]: /images/20221022/07ed1b4333144b9eba151f5c2ccb6490.png
[20210404145227379.png]: /images/20221022/4878d48a02da4f2aaa0be07cfe26bd25.png
[20210404145257338.png]: /images/20221022/8e6d9cc960944f1bb3bbe6c9d9966f68.png
[20210404145310825.png]: /images/20221022/f3cfbb6812a74da2b5dcc48f84c2ba17.png
[log_2n]: https://latex.codecogs.com/gif.latex?%5Clog_2n