1.概念:
归并:将两个或两个以上的有序序列合并成一个有序序列的过程。
归并排序的主要操作是归并,其主要思想是:将若干有序序列逐步归并,最终得到一个有序序列。
两路归并
假设待归并的两个有序表长度分别为m和L,则两路归并后,新的有序表长度为m+L
两路归并操作至多只需要m+L次移位和m+L次比较
因此两路归并的时间复杂度为O(m+L)
2.基本思想:
二路归并排序的基本思想(自底向上的非递归算法,也有通过递归实现的)将具有n个待排序记录的序列看成是n个长度为1的有序序列;然后进行两两归并,得到n/2个长度为2的有序序列;再进行两两归并,得到n/4个长度为4的有序序列;直至得到1个长度为n的有序序列为止。
3.算法性能:
(二路)归并排序算法性能分析
▪ 时间性能:
一趟归并操作是将A[1]-A[n]中相邻的长度为h的有序序列进行两两归并,并把结果存放到B[1]-B[n]中,这需要O(𝒏)时间。整个归并排序需要进𝒍𝒐𝒈𝟐𝒏趟,因此,总的时间代价是O(𝒏𝒍𝒐𝒈𝟐𝒏)。
▪ 空间性能:
算法在执行时,需要占用与原始记录序列同样数量的存储空间,因此空间复杂度为O(𝒏)。
▪ 归并排序是一种稳定的排序方法。
4.C++程序实现:
1 | #include <iostream> |
示例结果:
参考文章:
1.二路归并排序简介及其并行化
2.数据结构-二路归并及归并排序
3.归并排序 详解
4.白话经典算法系列之五 归并排序的实现