您好,欢迎访问代理记账网站
移动应用 微信公众号 联系我们

咨询热线 -

电话 15988168888

联系客服
  • 价格透明
  • 信息保密
  • 进度掌控
  • 售后无忧

找第二大数 <算法详解(卷1) 问题1.5>

假设有一个包含那个不同的数的未排序数组,其中你是2的整数次方。提供一种算法,确认数组中第二大的数,最大只能使用n+log2(n)-2次比较。

提要:将数组array对半分割,一直对半分割成最小的只有2个数的小数组,然后进行小数组排序,此时需要比较的次数是n/2

小数组排序完成后将相邻两个小数组进行合并,取最大两个数有序的放在合并后数组的前2位,然后继续重复,小数组的长度len由2,4,8...一直变大到n,排序完成,第二大数则为array[1]。

void miniArraySort(int *arr,int begin,int len){
    int tmp;
    if(len==2){             
        if(arr[begin]<arr[begin+len-1]){
            tmp=arr[begin+len-1];
            arr[begin+len-1] = arr[begin];
            arr[begin] = tmp;
        }
    }else{  
        if(arr[begin]<arr[begin+len/2+1]){
            tmp = arr[begin];
            arr[begin]=arr[begin+len/2];
            arr[begin+len/2] = tmp;
            tmp = arr[begin+1];
            arr[begin+1] = arr[begin+len/2+1];
            arr[begin+len/2+1] = tmp;
        }else if (arr[begin]<arr[begin+len/2]) {
            tmp = arr[begin+len/2];
            arr[begin+len/2] = arr[begin+1];
            arr[begin+1]=arr[begin];
            arr[begin] = tmp;
        }else  if(arr[begin+1]<arr[begin+len/2]){
            tmp = arr[begin+len/2];
            arr[begin+len/2] = arr[begin+1];
            arr[begin+1] = tmp;
        }
    }
}

void genericSort(int* a,int n){
    for(int l=2;l<=n;l=2*l)                
    {
        for(int begin=0;begin+l<=n;begin=begin+l){      
            miniArraySort(a,begin,l);
        }
    }
}


分享:

低价透明

统一报价,无隐形消费

金牌服务

一对一专属顾问7*24小时金牌服务

信息保密

个人信息安全有保障

售后无忧

服务出问题客服经理全程跟进