有什么算法能判断一个数组是否有序?

lost_templar

std::adjacent_find

1. template< typename Itor >
   
2. bool is_in_order( Itor begin, Itor end )
   
3. {
   
4.     if ( std::distance( begin, end ) < 3 ) return true;
   
5. 
   
6.     typedef typename std::iterator_traits<Itor>::value_type value_type;
   
7.     if ( *begin < *(begin+1) )
   
8.         return end == std::adjacent_find( begin, end, []( value_type const& lhs, value_type const& rhs ){ return lhs >= rhs; } );
   
9.     if ( *begin > *(begin+1) )
   
10.         return end == std::adjacent_find( begin, end, []( value_type const& lhs, value_type const& rhs ){ return lhs <= rhs; } );
    
11.     return is_in_order( begin+1, end );
    
12. }

复制代码

徒手写的，没有测试

captivated

O(N).

5 字节够了吗

MMMIX

回复 1# udodoo


    你排个序，再比较一下就有了。或者自己写个，从第一个到最后一个，两两比较，一旦出现逆序，就说明其非有序。

Susake_

...

captivated

回复 6# udodoo


    so u ka. 多谢告知. 算法复杂度多少...

myworkstation

回复 7# captivated


    因为逐个元素的比较所以是O(n)，理想情况下如果前两个元素非序那么马上可以就可以得到结果。