type
status
category
date
slug
summary
tags
icon
Last edited time
May 21, 2023 07:57 AM
什么是归并排序
归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用==分治法==(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。归并排序是一种==稳定的==排序方法。
归并排序的实现由两种方法: 自上而下的递归(所有递归的方法都可以用迭代重写,所以就有了第 2 种方法); 自下而上的迭代;
实现方式
2-路归并排序
假定待排序表含有 n 个记录,则可以看成是 n 个有序的子表,每个子表长度为 1, 然后两两 归并,得到个长度为2或1的有序表;再两两归并,……如此重复,直到合并成一个长度为 n 的有序表为止,这种排序方法称为
2-路归并排序
。例子:排序49、38、65、97、76、13、27
(1)首先将整个序列的每个关键字看成一个单独的有序的子序列
(2)两两归并,49 和 38 归并成{38 49} ,65 和 97 归并成{65 97},76 和 13 归并成{76,13}, 27 没有归并对象
(3)两两归并,{38 49) 和 {65 97}归并成{38 49 65 97}, {13,76} 和 27 归并成{13 27 76}
(4)两两归并,{38 49 65 97} 和{13 27 76} 归并成{13 27 38 49 65 76 97}
关于归并排序的性能参数
1、时间复杂度
2、空间复杂度
3、是否稳定
稳定
4、适用于何类型存储
顺序存储和链式存储
代码实现
C++:
- 作者:Jimmy Huang
- 链接:https://huangjihao.com/1c6e11ee-7c0b-4b42-b2f3-4bc6da21e10b
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议,转载请注明出处。