5.归并排序和基数排序

归并排序

归并排序与上述基于交换、选择等排序的思想不一样, “归并” 的含义是将两个或两个以上 的有序表合并成一个新的有序表。假定待排序表含有 $n$ 个记录, 则可将其视为 $n$ 个有序的子表, 每个子表的长度为 1 , 然后两两归并, 得到 $\lceil n / 2\rceil$ 个长度为 2 或 1 的有序表; 继续两两归并.......如 此重复, 直到合并成一个长度为 $n$ 的有序表为止, 这种排序方法称为 2 路归并排序。

image.png

2 路归并排序算法的性能分析如下:
空间效率: Merge () 操作中, 辅助空间刚好为 $n$ 个单元, 所以算法的空间复杂度为 $O(n)$ 。
时间效率: 每趟归并的时间复杂度为 $O(n)$, 共需进行 $\left\lceil\log _{2} n\right\rceil$ 趟归并, 所以算法的时间复杂 度为 $O\left(n \log _{2} n\right)$ 。
稳定性: 由于 Merge () 操作不会改变相同关键字记录的相对次序, 所以 2 路归并排序算法 是一种稳定的排序方法。

注意

一般而言, 对于 $N$ 个元素进行 $k$ 路归并排序时, 排序的趟数 $m$ 满足 $k^{m}=N$, 从而 $m=\log_{k}N$,又考虑到$m$为整数，所以$m=\left\lceil \log_{k}N \right\rceil$

基数排序

不基于比较和移动进行排序,而基于关键字各位的大小进行排序。

【课件】8.5.2基数排序

---

基数排序算法的性能分析如下。
空间效率: 一趟排序需要的辅助存储空间为 $r$ ( $r$ 个队列: $r$ 个队头指针和 $r$ 个队尾指针), 但 以后的排序中会重复使用这些队列, 所以基数排序的空间复杂度为 $O(r)$ 。
时间效率: 基数排序需要进行 $d$ 趟分配和收集, 一趟分配需要 $O(n)$, 一趟收集需要 $O(r)$, 所 以基数排序的时间复杂度为 $O(d(n+r))$, 它与序列的初始状态无关。
稳定性: 对于基数排序算法而言, 很重要一点就是按位排序时必须是稳定的。因此, 这也保 证了基数排序的稳定性。