网站链接: element-ui dtcms
当前位置: 首页 > 技术博文  > 技术博文

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

2021/6/28 4:16:21 人评论

假设有一个包含那个不同的数的未排序数组,其中你是2的整数次方。提供一种算法,确认数组中第二大的数,最大只能使用nlog2(n)-2次比较。 提要:将数组array对半分割,一直对半分割成最小的只有2个数的小数组,然…

假设有一个包含那个不同的数的未排序数组,其中你是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);
        }
    }
}

上一篇:学习周记12

下一篇:2021-06-28

相关资讯

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?