求一取最大值得算法！！常见排序算法不要。

cxytz01

后期数组可能会增大，不仅限于1024，而是上万。

而且比较函数是放在for( ; ;   )中的。

想看看有什么时间复杂度低的算法。

linux_c_py_php 发表于 2013-01-09 19:20
排序干嘛... 扫一遍不就知道了?

cxytz01

如果是遍历一遍就简单了，

但问题是是无限遍历

for(;  ; ) {

  某些操作使某个数组元素值变化

  取最大值...     数组目前是1024个元素，后期会扩展成1万个 以上。
   
  使用最大值



}


嗯，和排序无关，我想错了。

ahui886 发表于 2013-01-10 10:50
求个最大值，遍历一遍不就出来了？跟排序有啥关系呢？

cokeboL

回复 12# cxytz01


一楼说永远是1024，现在又说后期可能上万，，，，到底闹哪般？

请把需求一次性描述清楚，包括数组内容，比如：数字？字符串？用于比较大小的函数？

这样才可以分析你对数组的存取方式，比如哈希之类的，要提供需求的完整描述，然后

同时思考设计合理的存和取的方式，然后才能有明确答案

star_in_sky

使用大顶堆的算法，对现有的数组进行建堆操作。这样取最大值的就是O(1)操作。

基本的逻辑代码：

(以1024个元素为例子)

1. your_function_impl(.............)
   
2. {
   
3.     int number[1024];
   
4.    
   
5.     create_max_heap( number,1024 )
   
6.    
   
7.     for(;;)
   
8.    {
   
9.         if ( number中某个元素改动 )
   
10.              adjust_max_heap( number,1024 )
    
11.         
    
12.          max_value = number[0];
    
13.          
    
14.          execute other tasks.
    
15.     }
    
16. }

复制代码

cokeboL

回复 12# cxytz01


另外，最快的取一最大值算法，我觉得应该单独设立一变量保存最大值的下标，比如：

static int MAX_VAL_ADDR = -1;

做insert(element)操作的时候

xx  insert(element)
{
    ...
    if(-1 == MAX_VAL_ADDR)
    {
        MAX_VAL_ADDR = insert_addr;
    }
    else
    {
        if(element > val_array[MAX_VAL_ADDR])
        {
            MAX_VAL_ADDR = insert_addr;
        }
    }
}

int get_max_val_addr()
{
    return MAX_VAL_ADDR；
}
这样在取的时候复杂度O(1)

cokeboL

回复 16# cokeboL


    不过要看你支持不支持delete操作，否则delete时候还是要考虑

hellioncu

cxytz01 发表于 2013-01-10 10:51
是啊，很难。你搞出个给我看看。

不要告诉下面的代码

自己需求都不说清楚，还这种口气，懒得给你方法了

cokeboL

回复 17# pmerofc


楼主都能数数上万了， 记得俺幼儿园第一堂数学课作业就是数数，而且只要数到一百，第二天

老师让挨个同学背诵1-100，好怀念~