归并排序
本页面将简要介绍归并排序。
简介¶
归并排序(英语:merge sort)是一种采用了 分治 思想的排序算法。
工作原理¶
归并排序分为三个步骤:
- 将数列划分为两部分;
- 递归地分别对两个子序列进行归并排序;
- 合并两个子序列。
不难发现,归并排序的前两步都很好实现,关键是如何合并两个子序列。注意到两个子序列在第二步中已经保证了都是有序的了,第三步中实际上是想要把两个 有序 的序列合并起来。
性质¶
归并排序是一种稳定的排序算法。
归并排序的最优时间复杂度、平均时间复杂度和最坏时间复杂度均为 O(n\log n)。
归并排序的空间复杂度为 O(n)。
代码实现¶
伪代码¶
\begin{array}{ll}
1 & \textbf{Input. }\text{待排序的数组}A\text{和用作临时存储的数组}T\\
2 & \textbf{Output. }\text{数组}A\text{中的元素将会按照不减的顺序进行稳定排序}\\
3 & \textbf{Method.}\\
4 & \text{merge}(A,\ T)\\
5 & \qquad\text{merge0}(A,\ T,\ 0,\ A.length)\\
6 & \text{merge0}(A,\ T,\ ll,\ rr)\\
7 & \qquad \textbf{if}\ \ rr - ll \leqslant 1\\
8 & \qquad\qquad \textbf{return}\\
9 & \qquad mid \gets \large\lfloor\frac{ll+rr}{2}\rfloor\\
10& \qquad\text{merge0}(A,\ T,\ ll,\ mid)\\
11&\qquad\text{merge0}(A,\ T,\ mid,\ rr)\\
12&\\
13&\qquad p \gets ll\\
14&\qquad q \gets mid\\
15&\qquad\textbf{for}\text{ each } i \text{ in the } ll\dots rr-1\\
16&\qquad\qquad\textbf{if}\ p\geqslant mid\ or\ q < rr\ and\ A[q] < A[p]\\
17&\qquad\qquad\qquad T[i] \gets A[q]\\
18&\qquad\qquad\qquad q \gets q+1\\
19&\qquad\qquad\textbf{else}\\
20&\qquad\qquad\qquad T[i] \gets A[p]\\
21&\qquad\qquad\qquad p \gets p+1\\
22&\qquad \text{copy }T[ll\dots rr-1] \text{ to } A[ll\dots rr-1]\\
\end{array}
C++¶
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
|
Python¶
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
|
逆序对¶
归并排序还可以用来求逆序对的个数。
所谓逆序对,就是对于一个数组 a,满足 a_{i} > a_{j} 且 i < j 的数对 (i, j)。
代码实现中注释掉的 ans += mid - p
就是在统计逆序对个数。具体来说,算法把靠后的数放到前面了(较小的数放在前面),所以在这个数原来位置之前的、比它大的数都会和它形成逆序对,而这个个数就是还没有合并进去的数的个数,即 mid - p
。
另外,逆序对也可以用 树状数组、线段树 等数据结构求解。这三种方法的时间复杂度都是 O(n \log n)。
外部链接¶
build本页面最近更新:,更新历史
edit发现错误?想一起完善? 在 GitHub 上编辑此页!
people本页面贡献者:OI-wiki
copyright本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供,附加条款亦可能应用