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 )
以下是所有 STL sort 算法函数的名字列 表: 功能描述 sort 对给定区间所有元素进行排序 stable_sort 对给定区间所有元素进行稳定排序 partial_sort 对给定区间所有...
2008-03-13 1341 STL——p... 2008-04-16 0857 零散知识... ...partial_sort 对给定区间所有元素部分排序 partial_sort_copy 对给定区间复制并...
C++ partial_sort_copy_计算机软件及应用_IT/计算机_专业资料。C++ partial_sort_copy 将 range1 中的 range2_n 个元素复制到 range2 中并按 comp()为 true...
C++ partial_sort_copy_计算机软件及应用_IT/计算机_专业资料。C++ partial_sort_copy 将 range1 中的 range2_n 个元素复制到 range2 中并按 comp()为 true...
热门文档