C++ 算法 partial_sort()函数

C++算法 partial_sort() 函数用于将范围[first, last)内的元素重新排列，使得第一个和中间元素之间的元素被排序，而中间和最后元素之间的元素顺序未指定。

对于第一个版本，元素是使用运算符 < 进行比较，对于第二个版本，元素是使用 comp 进行比较。

语法

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

custom (2)      template <class RandomAccessIterator, class Compare>
                      void partial_sort (RandomAccessIterator first, RandomAccessIterator middle,
                           RandomAccessIterator last, Compare comp);

参数

first : 指向要进行部分排序的范围中第一个元素的随机访问迭代器。

last : 指向要进行部分排序的范围中最后一个元素之后的随机访问迭代器。

middle : 指向要进行排序的子范围中最后一个元素之后的随机访问迭代器。

comp : 一个用户定义的二元谓词函数，接受两个参数并返回true，如果两个参数按顺序排列，则返回false。它遵循严格的弱排序规则来排序元素。

返回值

无

复杂度

平均复杂度小于first和last之间的距离的线性对数。执行高达N*log(M)次元素比较，其中N = last – first，M = middle – first。

数据竞争

[first, last)范围内的对象会被改变。

异常

如果任何元素比较、元素交换（或移动）或迭代器上的操作引发异常，该函数会抛出异常。

注意：无效的参数会导致未定义行为。

示例1

让我们看一个简单的示例来演示partial_sort()的使用：

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
  vector<int> v = {3, 1, 4, 2, 5};

    cout<<"Before sorting: ";
    for_each(v.begin(), v.end(), [](int x) {
    cout << x << " ";
  });

    partial_sort(v.begin(), v.begin() + 2, v.end());

  cout<<"\nAfter sorting:  ";
  for_each(v.begin(), v.end(), [](int x) {
    cout << x << " ";
  });

  return 0;
}

输出：

Before sorting: 3 1 4 2 5 
After sorting:  1 2 4 3 5

示例2

让我们看另一个简单的示例：

#include <iostream>     // std::cout
#include <algorithm>    // std::partial_sort
#include <vector>       // std::vector

using namespace std;

bool myfunction (int i,int j) { return (i<j); }

int main () {
  int myints[] = {9,8,7,6,5,4,3,2,1};
  vector<int> myvector (myints, myints+9);

  // using default comparison (operator <):
  partial_sort (myvector.begin(), myvector.begin()+5, myvector.end());

  // using function as comp
  partial_sort (myvector.begin(), myvector.begin()+5, myvector.end(),myfunction);

  // print out content:
  cout << "myvector contains:";
  for (vector<int>::iterator it=myvector.begin(); it!=myvector.end(); ++it)
    cout << ' ' << *it;
  cout << '\n';

  return 0;
}

输出：

myvector contains: 1 2 3 4 5 9 8 7 6

示例3

让我们来看一个默认版本的简单示例：

#include <iostream>
#include <algorithm>
#include <functional>
#include <vector>

using namespace std ;

int main()
{
    const int VECTOR_SIZE = 8 ;

    // Define a template class vector of int
    typedef vector<int> IntVector ;

    //Define an iterator for template class vector of strings
    typedef IntVector::iterator IntVectorIt ;

    IntVector Numbers(VECTOR_SIZE) ;

    IntVectorIt start, end, it ;

    // Initialize vector Numbers
    Numbers[0] = 4 ;
    Numbers[1] = 10;
    Numbers[2] = 70 ;
    Numbers[3] = 30 ;
    Numbers[4] = 10;
    Numbers[5] = 69 ;
    Numbers[6] = 96 ;
    Numbers[7] = 7;

    start = Numbers.begin() ;   // location of first
                                // element of Numbers

    end = Numbers.end() ;       // one past the location
                                // last element of Numbers

    cout << "Before calling partial_sort\n" << endl ;

    // print content of Numbers
    cout << "Numbers { " ;
    for(it = start; it != end; it++)
        cout << *it << " " ;
    cout << " }\n" << endl ;

    // sort the smallest 4 elements in the sequence
    partial_sort(start, start+4, end) ;

    cout << "After calling partial_sort\n" << endl ;

    cout << "Numbers { " ;
    for(it = start; it != end; it++)
        cout << *it << " " ;
    cout << " }\n" << endl ;

   return 0; 
}

输出：

Before calling partial_sort

Numbers { 4 10 70 30 10 69 96 7  }

After calling partial_sort

Numbers { 4 7 10 10 70 69 96 30  }

示例4

让我们来看一个简单的自定义（谓词）版本的示例：

#include <iostream>
#include <algorithm>
#include <functional>
#include <vector>

using namespace std ;

int main()
{
    const int VECTOR_SIZE = 8 ;

    // Define a template class vector of int
    typedef vector<int> IntVector ;

    //Define an iterator for template class vector of strings
    typedef IntVector::iterator IntVectorIt ;

    IntVector Numbers(VECTOR_SIZE) ;

    IntVectorIt start, end, it ;

    // Initialize vector Numbers
    Numbers[0] = 4 ;
    Numbers[1] = 10;
    Numbers[2] = 70 ;
    Numbers[3] = 30 ;
    Numbers[4] = 10;
    Numbers[5] = 69 ;
    Numbers[6] = 96 ;
    Numbers[7] = 7;

    start = Numbers.begin() ;   // location of first
                                // element of Numbers

    end = Numbers.end() ;       // one past the location
                                // last element of Numbers

    cout << "Before calling partial_sort\n" << endl ;

    // print content of Numbers
    cout << "Numbers { " ;
    for(it = start; it != end; it++)
        cout << *it << " " ;
    cout << " }\n" << endl ;

    // sort the smallest 4 elements in the sequence
    partial_sort(start, start+4, end, less<int>()) ;

    cout << "After calling partial_sort\n" << endl ;

    cout << "Numbers { " ;
    for(it = start; it != end; it++)
        cout << *it << " " ;
    cout << " }\n" << endl ;

    return 0;
}

输出：

Before calling partial_sort

Numbers { 4 10 70 30 10 69 96 7  }

After calling partial_sort

Numbers { 4 7 10 10 70 69 96 30  }