首页 > 其他分享 >归并排序

归并排序

时间:2024-03-09 12:23:18浏览次数:22  
标签:归并 log int 复杂度 数组 排序

归并排序分析

一、代码实现

void merge(int*a,int low,int mid,int high){
    int *b = new int [high-low+1];
    int i=low,j=mid+1,k=0;
    while (i<=mid&&j<=high){
        if(a[i]<a[j]){
            b[k++] = a[i++];
        } else
            b[k++] = a[j++];

    }
    while (i<=mid)
        b[k++] = a[i++];
    while (j<=high)
        b[k++] = a[j++];
    k=0;
    for (int l = low; l <=high; ++l) {
        a[l] = b[k++];
    }
    delete []b;
}
void merge_sort(int*a,int low,int high){
    if(low==high)
        return;
    else {
        int mid = (low+high)/2;
        merge_sort(a, low, mid);
        merge_sort(a,mid+1,high);
        merge(a,low,mid,high);
    }
}

思路讲解
把一个数组分为左右两段,分别对其进行排序,则接下来只需要对两个有序数组合并即可

二、复杂度

时间复杂度:O(N*log_2N)
空间复杂度:O(N)

  • 时间复杂度:归并排序会对数组做二分分割,合并时对数组元素进行遍历,所以时间复杂度为O(N*log_2N)
  • 空间复杂度:主要来自两个方面,一个是递归分割时调用栈帧log_2N,一个是合并数组时额外开的数组N,则空间复杂度为O(N)

标签:归并,log,int,复杂度,数组,排序
From: https://www.cnblogs.com/saopigqwq233/p/18062492

相关文章

  • Shell排序复杂度分析
    Shell排序复杂度分析1.大致思想可以把希尔排序看作是发牌员,给每人轮流发一张牌。需要给n个人发牌,每人从第二张开始分别进行插入排序,那么第一轮下来后,每人的牌就是有序的。接下来按照刚刚的发牌顺序把牌再收起来,减少人数,不断重复这个步骤,直到只剩下一个人,那么就是直接插入排序......
  • MYSQL学习笔记9: DQL排序查询(升降序)
    DQL排序查询select字段列表from表名orderby字段1排序方式1,字段2排序方式2;排序方式ASC升序(默认)DESC降序如果是多字段排序,第一个字段值相同,会根据第二个字段的值进行排序,以此类推按年龄降序排序select*fromworkersorderbyagedesc;......
  • 通达信超金钻大涨排序指标公式源码
    {通达信超金钻大涨排序指标公式源码}X_1:=DYNAINFO(15)/DYNAINFO(4)/FINANCE(46)*(DYNAINFO(4)-REF(CLOSE,1))/REF(CLOSE,1)*10000;今开%:=(OPEN/REF(CLOSE,1)-1)*100;X_7:=CLOSE>=ZTPRICE(REF(CLOSE,1),0.1);X_8:=BArslAstCOUNT(X_7);昨日涨停次数:REF(X_8,1),NODRAW;X_......
  • 通达信竞价绝杀排序指标公式
    {通达信竞价绝杀排序指标公式}{指标介绍:1.黄金甲信号稳定的创业板票(主力净额大于1500万,占比大于8%,流通市值小于80亿);2.情绪周期里面的三板以上的主板票(主力净额大于1500万,占比大于8%,流通市值小于150亿);3.昨日涨停的创业板票,今日高开(主力净额大于800万,占比大于8%,流通市值......
  • 6-12 奇偶分离排序(关注输出的空格处理)
    6-12奇偶分离排序(关注输出的空格处理)分数10作者王秀单位福州大学输入10个整数,完成一个函数使数据重新排序以后输出(也按空格分隔),要求:输出奇数在前偶数在后函数接口定义:voidsort_tarray(int*a);裁判测试程序样例:#include<cstdio>#include<iostream>#inclu......
  • mysql 按条件排序:order by 高级用法之case when, if 复杂排序
    转载自:https://blog.csdn.net/weixin_44684303/article/details/124445293实例1原始数据顺序需要的效果:学科按照顺序语文,数学,英语分数倒序演示创建表CREATETABLE`student_score`(`id`bigint(20)NOTNULLAUTO_INCREMENTCOMMENT'主键',`student_i......
  • 神经网络—拓扑排序
    输入格式第一行是两个整数n(1≤n≤100)和p。接下来n行,每行两个整数,第i+1行是神经元i最初状态和其阈值(Ui),非输入层的神经元开始时状态必然为0。再下面P行,每行由两个整数i,j及一个整数Wij,表示连接神经元i、j的边权值为Wij。输出格式输出文件包含若干行,每行有两个整数,......
  • 归并排序
    includeincludeusingnamespacestd;intn,a[100100],b[100100];templateinlinevoidread(type&x){x=0;boolflag(0);charch=getchar();while(!isdigit(ch))flag^=ch=='-',ch=getchar();while(isdigit(ch))x=(x<<1)+(x<<3)+(ch^48),c......
  • VUE GRID WITH COMPONENT排序
    父组件:<!--Anexampleofcreatingareusablegridcomponentandusingitwithexternaldata.--><scriptsetup>importDemoGridfrom'../components/Grid.vue'import{ref}from'vue'constsearchQuery=ref('')......
  • 33. 搜索旋转排序数组(中)
    目录题目二分搜索题目整数数组nums按升序排列,数组中的值互不相同。在传递给函数之前,nums在预先未知的某个下标k(0<=k<nums.length)上进行了旋转,使数组变为[nums[k],nums[k+1],...,nums[n-1],nums[0],nums[1],...,nums[k-1]](下标从0开始计数)。例如,[0,1......