那谁的技术博客

感兴趣领域:高性能服务器编程,存储,算法,Linux内核
随笔 - 210, 文章 - 0, 评论 - 1183, 引用 - 0
数据加载中……

[算法问题]寻找一个序列中第n大的元素

问题描述:给定一个序列,以及指定这个序列的一个范围,寻找这个范围之内第n大的元素,如果n大于这个范围之内的元素数量那么就返回-1.

这是快速排序算法中partiton算法的一个应用,不断的分割序列,如果分割的位置正好是要找的位置,那么返回结果,否则视情况在前半部分和后半部分继续查找,当然这个时候n值也要相应的变化了~~

/* *******************************************************************
    created:    2006/07/04
    filename:     nthElement.cpp
    author:        李创
                
http://www.cppblog.com/converse/

    purpose:    得到一个序列某个范围以内的第n个元素的算法演示
                提供了这个算法的递归和非递归的实现算法
                同时为了测试之用提供了堆算法,用于在找到第N个元素之后
                和排序之后的数组对应位置元素进行比较以测试代码是否正确
********************************************************************
*/


#include 
< stdio.h >
#include 
< stdlib.h >
#include 
< time.h >

//  交换元素
void  Swap( int   * a,  int   * b)
{
    
int  temp;

    temp 
=   * a;
    
* a    =   * b;
    
* b    =  temp;
}


//  打印数组元素
void  DisplayArray( int  array[],  int  length)
{
    
int  i;

    
for  (i  =   0 ; i  <  length; i ++ )
    
{
        printf(
" array[%d] = %d\n " , i, array[i]);
    }

}


//  随机创建一个数组
void  CreateNewArray( int  array[],  int  length)
{
    
for  ( int  i  =   0 ; i  <  length; i ++ )
    
{
        array[i] 
=  rand()  %   256 ;
    }

}


//  对一个给定范围的子序列选定一个枢纽元素,执行完函数之后返回分割元素所在的位置,
//  在分割元素之前的元素都小于枢纽元素,在它后面的元素都大于这个元素
int  Partition( int  array[],  int  low,  int  high)
{
    
//  采用子序列的第一个元素为枢纽元素
    
//  非常奇怪,如果我把选择枢纽元素的算法改成注释掉的那一行那么就会出错(不是必现的)
    
//  难道枢纽元素的选择也会对这个算法产生影响?
    
//  我在快速排序算法中测试了这个函数,两种选择枢纽元素的算法最后得到的结果都是正确的~~
    
// int pivot = array[(low + high) / 2];
     int  pivot  =  array[low];

    
while  (low  <  high)
    
{
        
//  从后往前在后半部分中寻找第一个小于枢纽元素的元素
         while  (low  <  high  &&  array[high]  >=  pivot)
        
{
            
-- high;
        }


        
//  将这个比枢纽元素小的元素交换到前半部分
        Swap( & array[low],  & array[high]);

        
//  从前往后在前半部分中寻找第一个大于枢纽元素的元素
         while  (low  <  high  &&  array[low]  <=  pivot)
        
{
            
++ low;
        }


        
//  将这个比枢纽元素大的元素交换到后半部分
        Swap( & array[low],  & array[high]);
    }


    
//  返回枢纽元素所在的位置
     return  low;
}


//  寻找数组array中区间为[low, high]中的第n大的元素,
//  如果n大于这个区间的元素个数就返回-1
//  非递归实现,这个非递归的实现很是简单,就是把几个出口的递归调用改写成循环就好了~~
int  nthElement2( int  array[],  int  low,  int  high,  int  n)
{
    
if  (low  >  high  ||  n  <   1   ||  n  >  high  -  low  +   1 )
    
{
        
return   - 1 ;
    }


    
int  i;
    
while  ( 1 )
    
{
        i 
=  Partition(array, low, high);

        
if  (low  +  n  -   1   ==  i)
        
{
            
return  array[i];
        }

        
else   if  (low  +  n  -   1   <  i)
        
{
            
// return nthElement(array, low, i - 1, n);
            high  =  i  -   1 ;
        }

        
else   if  (low  +  n  -   1   >  i)
        
{
            
// return nthElement(array, i + 1, high, n - (i - low + 1));
            low  =  i  +   1 ;
            n 
=  n  -  (i  -  low  +   2 );
        }

    }

}


//  寻找数组array中区间为[low, high]中的第n大的元素,
//  如果n大于这个区间的元素个数就返回-1
//  递归实现
int  nthElement( int  array[],  int  low,  int  high,  int  n)
{
    
if  (low  >  high  ||  n  <   1   ||  n  >  high  -  low  +   1 )
    
{
        
return   - 1 ;
    }


    
int  i  =  Partition(array, low, high);

    
if  (low  +  n  -   1   ==  i)
    
{
        
return  array[i];
    }

    
else   if  (low  +  n  -   1   <  i)
    
{
        
return  nthElement(array, low, i  -   1 , n);
    }

    
else   if  (low  +  n  -   1   >  i)
    
{
        
return  nthElement(array, i  +   1 , high, n  -  (i  -  low  +   1 ));
    }

}


//  调整堆数组
//  array是待调整的堆数组,i是待调整的数组元素的位置,length是数组的长度
void  HeapAdjust( int  array[],  int  i,  int  length)
{
    
int  child, temp;

    
for  (temp  =  array[i];  2   *  i  +   1   <  length; i  =  child)
    
{
        child 
=   2   *  i  +   1 ;

        
//  得到子结点中较小的结点
         if  (child  !=  length  -   1   &&  array[child  +   1 >  array[child])
            
++ child;

        
//  如果较小的子结点大于父结点那么把较小的子结点往上移动,替换它的父结点
         if  (temp  <  array[child])
        
{
            array[i] 
=  array[child];
        }

        
else      //  否则退出循环
         {
            
break ;
        }

    }


    
//  最后把需要调整的元素值放到合适的位置
    array[i]  =  temp;
}

//  堆排序算法
void  HeapSort( int  array[],  int  length)
{
    
//  调整序列的前半部分元素,调整完之后第一个元素是序列的最大的元素
     for  ( int  i  =  length  /   2   -   1 ; i  >=   0 -- i)
    
{
        HeapAdjust(array, i, length);
    }


    
//  从最后一个元素开始对序列进行调整,不断的缩小调整的范围直到第一个元素
     for  ( int  i  =  length  -   1 ; i  >   0 -- i)
    
{
        
//  把第一个元素和当前的最后一个元素交换,
        
//  保证当前的最后一个位置的元素都是在现在的这个序列之中最大的
        Swap( & array[ 0 ],  & array[i]);

        
//  对当前的序列进行调整,调整完之后保证第一个元素是当前序列的最大值
        HeapAdjust(array,  0 , i);
    }

}


int  main( void )
{
    
int  array[ 10 ];
    srand(time(NULL));

    
int  n;
    printf(
" input n:\n " );
    scanf(
" %d " & n);

    
//  测试递归程序
    printf( " 测试算法的递归函数实现\n " );
    CreateNewArray(array, 
10 );
    DisplayArray(array, 
10 );
    
int  i  =  nthElement(array,  0 9 , n);
    
    HeapSort(array, 
10 );
    printf(
" after Heap Sort:\n " );
    DisplayArray(array, 
10 );

    printf(
" \nfind %d = %d\n " , n, i);
    
if  (array[n  -   1 ==  i)
    
{
        printf(
" found!!\n " );
    }


    
//  测试非递归函数的实现
    printf( " 测试算法的递归函数实现\n " );
    CreateNewArray(array, 
10 );
    DisplayArray(array, 
10 );
    i 
=  nthElement2(array,  0 9 , n);

    HeapSort(array, 
10 );
    printf(
" after Heap Sort:\n " );
    DisplayArray(array, 
10 );

    printf(
" \nfind %d = %d\n " , n, i);
    
if  (array[n  -   1 ==  i)
    
{
        printf(
" found!!\n " );
    }



    system(
" pause " );

    
return   0 ;
}

posted on 2006-07-08 02:04 那谁 阅读(3188) 评论(8)  编辑 收藏 引用 所属分类: 算法与数据结构

评论

# re: [算法问题]寻找一个序列中第n大的元素  回复  更多评论   

使用STL里面的partial_sort很简单的就可以得到一个序列中第N大的元素了。
2006-07-08 10:29 | 3×7=51

# re: [算法问题]寻找一个序列中第n大的元素  回复  更多评论   

犯错误了,使用STL里面的nth_element才是最好的办法
2006-07-08 10:59 | 3×7=51

# re: [算法问题]寻找一个序列中第n大的元素  回复  更多评论   

我不否认有现成的可以用,但是我更愿意去了解其中的原理~~
2006-07-08 12:38 | 创系

# re: [算法问题]寻找一个序列中第n大的元素  回复  更多评论   

恕我直言,我觉得你这种方法并不是个好方法。等有时间我跟你讨论一下这个问题还有什么解决方案。不过你可以去看下stl的实现(我自己还没看)。
2006-07-08 16:55 | 3×7=51

# re: [算法问题]寻找一个序列中第n大的元素  回复  更多评论   

赞楼主自己思考问题:)
2007-03-30 14:40 | wtommy

# re: [算法问题]寻找一个序列中第n大的元素  回复  更多评论   

// int pivot = array[(low + high) / 2];
采用这句的时候会出问题,在调试中发现,当pivot本身就是数组中最大值时,low和high的会全部循环完,而跳出循环,没有实现交换的目的;
可能是对算法理解有问题,不应该是low和high进行交换,应该是是和pivot进行交换
2007-06-18 20:14 | stream

# re: [算法问题]寻找一个序列中第n大的元素  回复  更多评论   

我觉得stream说的对,应该是和pivot交换。
2007-12-04 05:08 | alexandercer

# re: [算法问题]寻找一个序列中第n大的元素[未登录]  回复  更多评论   

用红黑树数组,在红黑树中的每个节点都加入左边和有边的节点的数目,如果比左节点数目大就向左走,比右边节点数目大,就减去这个数字再向右走,这样一直走下去就找到了
2015-02-01 22:25 | shawn

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理