Question

c语言算法设计

用分治算法来找出N个元素的序列中的第二大元素，并分析算法的时间复杂度

Answer 1

分析题目，查找第二大元素，首先就要知道最大的元素。所以我们可以先排序，这样就方便找它了。

分治法，就是把n规模的问题转换成k个相同性质的小问题解决的方法，常见的是二分法，数据结构中有折半插入排序。它的算法描述如下：

BinsertSort(Recordnode r[],int n)
{
     for(i=2;<=n;++i)  
           {
            r[0]=r[i];
            low=1;
            high=i-1;    
            while(low<=high)
                {
                    m=(low+high)/2
                        if(r[0]<r[m].key)
                            high=m-1;
                        else
                            low=m+1;
                  } 
for(j=i-1;j>=high+1;--j) 
r[j+1]=r[j]; 
r[high+1]=r[0]; 
} 
}

Answer 2

算法导论第9章，最坏是n，最好是logn

追问

算法呢

Answer 3

c语言算法
这元素的有，问题的