文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > IT/计算机 > 计算机软件及应用 > 2008-03-13 1341 STL——partial_sort使用
侵权投诉

2008-03-13 1341 STL——partial_sort使用

template <class RandomAccessIterator>
void partial_sort(RandomAccessIterator first,
RandomAccessIterator middle,
RandomAccessIterator last);

template <class RandomAccessIterator, class StrictWeakOrdering>
void partial_sort(RandomAccessIterator first,
RandomAccessIterator middle,
RandomAccessIterator last,
StrictWeakOrdering comp);
时间复杂度分析:

首先,partial_sort使用的是堆排序,建堆的时间复杂度为O(n),调整堆的时间度杂度为o(logn),如果调用
partial_sort时middle的值为last的值,则相当于调用sort,对所有元素排序,但是堆排序是稳定的排序。假如求的是m个
元素的partial_sort,则,o(n) + m*o(logn);

vs2005msdn中的例子:
#include <vector>
#include <algorithm>
#include <functional> // For greater<int>( )
#include <iostream>

// Return whether first element is greater than the second
bool UDgreater ( int elem1, int elem2 )
{
return elem1 > elem2;
}

int main( )
{
using namespace std;
vector <int> v1;
vector <int>::iterator Iter1;

int i,ii;
for ( i = 0 ; i <= 5 ; i++ )
v1.push_back( 2 * i );

for ( ii = 0 ; ii <= 5 ; ii++ )
v1.push_back( 2 * ii +1 );

cout << "Original vector:\n v1 = ( " ;
for ( Iter1 = v1.begin( ) ; Iter1 != v1.end( ) ; Iter1++ )
cout << *Iter1 << " ";
cout << ")" << endl;

partial_sort(v1.begin( ), v1.begin( ) + 6, v1.end( ) );
cout << "Partially sorted vector:\n v1 = ( " ;
for ( Iter1 = v1.begin( ) ; Iter1 != v1.end( ) ; Iter1++ )
cout << *Iter1 << " ";
cout << ")" << endl;

partial_sort(v1.begin( ), v1.begin( ) + 4, v1.end( ), greater<int>( ) );
cout << "Partially resorted (greater) vector:\n v1 = ( " ;
for ( Iter1 = v1.begin( ) ; Iter1 != v1.end( ) ; Iter1++ )
cout << *Iter1 << " ";
cout << ")" << endl;

// A user-defined (UD) binary predicate can also be used
partial_sort(v1.begin( ), v1.begin( ) + 8, v1.end( ), UDgreater );
cout << "Partially resorted (UDgreater) vector:\n v1 = ( " ;
for ( Iter1 = v1.begin( ) ; Iter1 != v1.end( ) ; Iter1++ )
cout << *Iter1 << " ";
cout << ")" << endl;
}

Original vector: v1 = ( 0 2 4 6 8 10 1 3 5 7 9 11 )Partially sorted vector: v1 = ( 0 1 2 3 4 5 10
8 6 7 9 11 )Partially resorted (greater) vector: v1 = ( 11 10 9 8 0 1 2 3 4 5 6 7 )Partially
resorted (UDgreater) vector: v1 = ( 11 10 9 8 7 6 5 4 0 1 2 3 )

第1页

你可能喜欢

热门文档

相关文档

  • 如何正确使用STL中的排序

    以下是所有 STL sort 算法函数的名字列 表: 功能描述 sort 对给定区间所有元素进行排序 stable_sort 对给定区间所有元素进行稳定排序 partial_sort 对给定区间所有...

  • 2008-03-13 0936 sort综述——所有关于sort的函数_免费...

    2008-03-13 1341 STL——p... 2008-04-16 0857 零散知识... ...partial_sort 对给定区间所有元素部分排序 partial_sort_copy 对给定区间复制并...

  • C++ partial_sort_copy

    C++ partial_sort_copy_计算机软件及应用_IT/计算机_专业资料。C++ partial_sort_copy 将 range1 中的 range2_n 个元素复制到 range2 中并按 comp()为 true...

  • C++ partial_sort_copy

    C++ partial_sort_copy_计算机软件及应用_IT/计算机_专业资料。C++ partial_sort_copy 将 range1 中的 range2_n 个元素复制到 range2 中并按 comp()为 true...

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email