归并排序

2021-02-14 16:16

阅读：479

标签：mergesort nlog lin inline 选择因此序列用两个归并排序

简述

归并排序与基于交换、选择等排序的思想不一样，“归并”的含义是将两个或两个以上的有序表组合成一个新的有序表。

算法思想

假定序列有n个记录，则可以将其看成是n个有序子序列，每个子序列的长度为1，然后两两合并，得到\(\lceil n/2 \rceil\)个长度为2或1的有序序列；再两两归并，······如此重复，直到合并成一个长度为n的有序表为止，这种方法被称为2-路归并排序。

故我们将整个算法分为两个部分，一个部分用来进行序列的归并，一个部分用来递归排序。归并的算法需要一个缓存数组，用来临时存放归并过程中的数据，归并过程中，每次从两个子序列中选择一个较小（或较大）的数放入缓存数组，需要注意的是，最后可能有部分子序列有剩余的元素，需要单独把这部分剩余元素置入缓存数组，最后再把缓存数组中的序列复制到原数组则完成归并。递归排序的算法使用两个边界数来划分递归的区间，每一趟划分都把序列划分为两个子序列，再对两个子序列分别排序，排序结束后，把两个子序列归并到一个序列中，完成一趟递归排序。

我们在这里使用了一个缓存数组，如果缓存数组在每一趟递归排序中分配，则每次递归排序的算法中需要进行缓存数组内存的分配与释放，反复多次，会造成较大的时间开销，故我们采用一次动态分配的数组作为缓存数组。

算法性能分析

空间效率：辅助空间需要n个单元，故空间复杂度为\(O(n)\)。
时间效率：每一趟归并的时间复杂度为\(O(n)\)，共需要\(\lceil log_2n \rceil\)趟归并，因此时间复杂度为\(O(nlog_2n)\)。
稳定性：merge函数不会改变大小相同的关键字相对次序，因此是一个稳定的算法。

C++实现

#include 
using namespace std;

// 归并两个子序列
void merge(int a[], int b[], int low, int mid, int high) {
    int i = low, j = mid + 1, k = low;
    while (i

归并排序

标签：mergesort nlog lin inline 选择因此序列用两个归并排序

原文地址：https://www.cnblogs.com/southernEast/p/12722578.html

上一篇：【葵花宝典】一天掌握Kubernetes

下一篇：maven项目生成的jar包运行java -jar 包名报错 Configuration problem: Unable to locate Spring NamespaceHandler for X

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：归并排序
文章链接：http://soscw.com/index.php/essay/55243.html

亲，登录后才可以留言！

归并排序

简述

算法思想

算法性能分析

C++实现

评论

热门文章

推荐文章

最新文章

置顶文章