专栏首页书山有路勤为径分治算法之归并排序

分治算法之归并排序

分治算法: 将一个规模为N的问题分解为K个规模较小的子问题,这些子问题互相独立且与原问题性质相同。求出子问题的解后进行合并,就可得到原问题的解。

一般步骤: 1.分解,将要解决的问题划分成若干规模较小的同类问题; 2.求解,当子问题划分得足够小时,用较简单的方法解决; 3.合并,安原问题的要求,将子问题的解逐层合并构成原问题的解。

归并排序复杂度分析

设有n个元素,n个元素归并排序的时 间T(n) 总时间 = 分解时间 + 解决子问题时间 + 合并时间 分解时间: 即对原问题拆解为两个子问 题的时间 复杂度O(n) 解决子问题时间: 即解决两个子问题 的时间 2T(n/2) 合并时间: 即对两个已排序数组归并 的时间 复杂度O(n) T(n) = 2T(n/2) + 2O(n) = 2T(n/2) + O(n) = O(n + 2n/2 + 4n/4 +...+n*1) = O(nlogn)

详细推导可以参看算法导论

void merge_sort_two_vec(std::vector<int> & sub_vec1,std::vector<int> &sub_vev2, std::vector<int> &sub_vec){
 }

void merge_sort(std::vector<int> & vec){
    if(vec.size() < 2){
        return ;//求解问题足够小时,直接求解
    }
    int mid = vec.size() / 2;
    std::vector<int> sub_vec1;
    std::vector<int> sub_vec2;
    for (int i = 0; i < mid; i++){
      sub_vec1.push_back(vec[i]);
    }
    for(int i =mid ; i < vec.size();i++){
    sub_vec2.push(vec[i]);
    }
    merge_sort(sub_vec1);
    merge_sort(sub_vec2);
    vec.clear();
    merge_sort_two_vec(sub_vec1,sub_vec2,vec);
}
测试
#include <stdio.h>
#include <algorithm>//生成随机数组,利用 std::sort测试归并排序
#include <assert.h>
int main(){
    std::vector<int> vec1;
    std::vector<int> vec2;
    srand(time(NULL));
for(int i = 0;i < 10000;i++){
    int num = (rand() * rand()) % 100003;
    vec1.push_back(num);
    vec2.push_back(num);
  
}
merge_sort(vec1);
std::sort(vec2.begin,vec2.end());
assert(vec1.size() == vec2.size());
for(int i =0;i< vec1.size();i++){
    assert(vec1[i] == vec2[i]);
}
return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 归并两个已排序数组

    已知两个已排序数组,将这两个数组合并为一个排序数组。设a[i]对应数组1的元素,b[j]对应数组2的元素,则a[i],b[j]哪个元素小即将它添加到结果数组中,...

    小飞侠xp
  • 逆序数

    LeetCode 315. Count of Smaller Numbers After Self

    小飞侠xp
  • k个排序链表的合并

    LeetCode 23. Merge k Sorted Lists 已知k个已排序链表头节点指针,将这k个链表合并,合并后仍为有序的,返 回合并后的头节点。

    小飞侠xp
  • 归并两个已排序数组

    已知两个已排序数组,将这两个数组合并为一个排序数组。设a[i]对应数组1的元素,b[j]对应数组2的元素,则a[i],b[j]哪个元素小即将它添加到结果数组中,...

    小飞侠xp
  • Linux AV1硬件视频解码将支持Intel Tiger Lake

    https://linuxreviews.org/Linux_AV1_Hardware_Video_Decoding_Support_Ready_For_Int...

    LiveVideoStack
  • Linux AV1硬件视频解码将支持Intel Tiger Lake

    将于2020年9月推出的英特尔Tiger Lake处理器将是首款具有集成显卡的英特尔处理器,该显卡支持AV1硬件解码,但不进行编码。 Linux在3月将会把对A...

    LiveVideoStack
  • C/C++黑魔法-另类switch

    Qt君
  • 注册域名就完事儿?有它更安心

    如果说到QQ,你会联想到什么? QQ——它的品牌 企鹅——它的商标 QQ.COM——它的域名 域名是为了更简单快捷的指向品牌 商标则是为了保护、标识品牌 说到...

    腾讯云DNSPod团队
  • SQL优化案例-分区索引之无前缀索引(六)

    无前缀索引:分区索引不包含分区字段就叫无前缀索引,那么什么时候用无前缀索引和前缀索引呢?

    沃趣科技
  • 1.3 ASM-简介-结构

    本部文档由两部分组成。第一部分涵盖了核心API,即asm、asm-util、asm-commons包。 第二部分涵盖了tree API,即asm-tree、as...

    白凡

扫码关注云+社区

领取腾讯云代金券