C++ stl算法——partition

函数声明

1
2
template< class ForwardIt, class UnaryPredicate >
ForwardIt partition( ForwardIt first, ForwardIt last, UnaryPredicate p );

作用

对[first, last)元素进行处理,使得满足p的元素移到[first, last)前部,不满足的移到后部,返回第一个不满足p元素所在的迭代器,如果都满足的话返回last

可能的实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
template<class ForwardIt, class UnaryPredicate>
ForwardIt partition(ForwardIt first, ForwardIt last, UnaryPredicate p)
{
first = std::find_if_not(first, last, p);
if (first == last) return first;

for(ForwardIt i = std::next(first); i != last; ++i){
if(p(*i)){
std::iter_swap(i, first);
++first;
}
}
return first;
}

复杂度

  1. 一次循环,所以时间复杂度为O(N)
  2. 最坏会进行O(N)次swap, (有且仅有第一个为不满足的情况)

示例

使用partition进行一般操作,并用partition实现了一个快排

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>
#include <forward_list>

template <class ForwardIt>
void quicksort(ForwardIt first, ForwardIt last)
{
if(first == last) return;
auto pivot = *std::next(first, std::distance(first,last)/2);
ForwardIt middle1 = std::partition(first, last,
[pivot](const auto& em){ return em < pivot; });
quicksort(first, middle1);
quicksort(std::next(middle1, 1), last);
}

int main()
{
std::vector<int> v = {0,1,2,3,4,5,6,7,8,9};
std::cout << "Original vector:\n ";
for (int elem : v) std::cout << elem << ' ';

auto it = std::partition(v.begin(), v.end(), [](int i){return i % 2 == 0;});

std::cout << "\nPartitioned vector:\n ";
std::copy(std::begin(v), it, std::ostream_iterator<int>(std::cout, " "));
std::cout << " * ";
std::copy(it, std::end(v), std::ostream_iterator<int>(std::cout, " "));

std::forward_list<int> fl = {1, 30, -4, 3, 5, -4, 1, 6, -8, 2, -5, 64, 1, 92};
std::cout << "\nUnsorted list:\n ";
for(int n : fl) std::cout << n << ' ';
std::cout << '\n';

quicksort(std::begin(fl), std::end(fl));
std::cout << "Sorted using quicksort:\n ";
for(int fi : fl) std::cout << fi << ' ';
std::cout << '\n';
}

输出

1
2
3
4
5
6
7
8
Original vector:
0 1 2 3 4 5 6 7 8 9
Partitioned vector:
0 8 2 6 4 * 5 3 7 1 9
Unsorted list:
1 30 -4 3 5 -4 1 6 -8 2 -5 64 1 92
Sorted using quicksort:
-8 -5 -4 -4 1 1 1 2 3 5 6 30 64 92