当前位置：首页 -> 基础 -> c++编程基础

C++ 算法库(4) 排序操作(一)

2014-11-24 08:23:44 · 作者: · 浏览: 1
标签: 算法 排序 操作

排序操作：

is_sorted C++11 检测指定范围是否已排序
is_sorted_until C++11 返回最大已排序子范围
nth_element 部份排序指定范围中的元素，使得范围按给定位置处的元素划分
partial_sort 部份排序
partial_sort_copy 拷贝部分排序的结果
sort 排序
stable_sort 稳定排序

is_sorted

检测指定范围是否已排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// is_sorted example
#include // std::cout
#include // std::is_sorted, std::prev_permutation
#include // std::array

int main () {
std::array foo {2,4,1,3};

do {
// try a new permutation:
std::prev_permutation(foo.begin(),foo.end());

// print range:
std::cout << "foo:";
for (int& x:foo) std::cout << ' ' << x;
std::cout << '\n';

} while (!std::is_sorted(foo.begin(),foo.end()));

std::cout << "the range is sorted!\n";

return 0;
}

输出：

1
2
3
4
5
6
7
8
9
10
11
foo: 2 3 4 1
foo: 2 3 1 4
foo: 2 1 4 3
foo: 2 1 3 4
foo: 1 4 3 2
foo: 1 4 2 3
foo: 1 3 4 2
foo: 1 3 2 4
foo: 1 2 4 3
foo: 1 2 3 4
the range is sorted!


is_sorted_until

返回最大已排序子范围

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
// is_sorted_until example
#include // std::cout
#include // std::is_sorted_until, std::prev_permutation
#include // std::array

int main () {
std::array foo {2,4,1,3};
std::array ::iterator it;

do {
// try a new permutation:
std::prev_permutation(foo.begin(),foo.end());

// print range:
std::cout << "foo:";
for (int& x:foo) std::cout << ' ' << x;
it=std::is_sorted_until(foo.begin(),foo.end());
std::cout << " (" << (it-foo.begin()) << " elements sorted)\n";

} while (it!=foo.end());

std::cout << "the range is sorted!\n";

return 0;
}

输出：

1
2
3
4
5
6
7
8
9
10
11
foo: 2 3 4 1 (3 elements sorted)
foo: 2 3 1 4 (2 elements sorted)
foo: 2 1 4 3 (1 elements sorted)
foo: 2 1 3 4 (1 elements sorted)
foo: 1 4 3 2 (2 elements sorted)
foo: 1 4 2 3 (2 elements sorted)
foo: 1 3 4 2 (3 elements sorted)
foo: 1 3 2 4 (2 elements sorted)
foo: 1 2 4 3 (3 elements sorted)
foo: 1 2 3 4 (4 elements sorted)
the range is sorted!


nth_element

部份排序指定范围中的元素，使得范围按给定位置处的元素划分

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
// nth_element example
#include // std::cout
#include // std::nth_element, std::random_shuffle
#include // std::vector

bool myfunction (int i,int j) { return (i
int main () {
std::vector myvector;

// set some values:
for (int i=1; i<10; i++) myvector.push_back(i); // 1 2 3 4 5 6 7 8 9

std::random_shuffle (myvector.begin(), myvector.end());

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

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

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

return 0;
}

输出：

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


partial_sort

部份排序

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
// partial_sort example
#include // std::cout
#include // std::partial_sort
#include // std::vector

bool myfunction (int i,int j) { return (i
int main () {
int myints[] = {9,8,7,6,5,4,3,2,1};
std::vector myvector (myints, myints+9);

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

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

// print out content:
std::cout << "myvector contains:";
for (std::vector ::iterator it=myvector.begin(); it!=