partial_sort

Makale
03/26/2013

Bir aralıktaki küçük öğeleri belirli bir sayıda nondescending bir sipariş veya ikili karşılaştırma tarafından belirtilen bir sıralama ölçütü göre düzenler.

template<class RandomAccessIterator>
   void partial_sort(
      RandomAccessIterator first, 
      RandomAccessIterator sortEnd,
      RandomAccessIterator last
   );
template<class RandomAccessIterator, class BinaryPredicate>
   void partial_sort(
      RandomAccessIterator first, 
      RandomAccessIterator sortEnd,
      RandomAccessIterator last
      BinaryPredicate comp
   );

Parametreler

first
Sıralanan aralıkta ilk öğenin konumunu adresleme bir rasgele erişim Yineleyici.
sortEnd
Sıralanacak alt aralığı son öğesinde geçmiş konum adresleme bir rasgele erişim Yineleyici.
last
Kısmen sıralanacak konumu bir son öğe geçen aralıktaki adresleme bir rasgele erişim Yineleyici.
comp
Sıralama içinde birbirini izleyen öğeleri tarafından yerine getirilmesi için karşılaştırma ölçütü tanımlayan kullanıcı tanımlı işlevin doðrulama nesnesi.İkili karşılaştırma iki baðýmsýz deðiþken alýr ve döner doğru memnun, ve yanlış tatmin olduğunda.

Notlar

Başvurulan aralığı geçerli olması gerekir; Tüm işaretçiler dereferenceable ve sıra içinde son konuma birinciden erişilebildiğinden tarafından incrementation.

Öğeleri eşdeğer olan, ancak şart değil eşit, ikisi de varsa diğer azdır.Sıralama algoritması kararlı değil ve göreli eşdeğer öğelerinin sıralamasını korunacaktır olduğunu garanti etmez.Algoritma stable_sort orijinal sipariş koru.

The average partial sort complexity is O((last-first) log (sortEnd-first)).

Örnek

// alg_partial_sort.cpp
// compile with: /EHsc
#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;
   for ( i = 0 ; i <= 5 ; i++ )
   {
      v1.push_back( 2 * i );
   }

   int ii;
   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;

   // To partially sort in descending order, specify binary predicate
   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;
}