排序

Coddy C++ 标准模板库课程的第 19 课，共 23 课。

排序通常是指将容器中的元素重新排列成符合逻辑的顺序。

排序是通过函数应用于数据的最基础、最重要的技术之一。也就是说，排序可以按照我们想要的特定方式，将一系列元素按逻辑顺序排列。

排序算法有助于处理数据，也能帮助解决许多数学和编程问题。

*要使用这些方法，我们需要在 C++ 文件顶部使用 #include <algorithm> 引入 algorithm 头文件。

你将学习 STL 算法库中用于排序数据的内置函数。
我们将学习以下三个函数：

sort()
is_sorted()
partial_sort()

`sort` 方法

STL 的 sort() 方法会对给定范围内的内容进行排序。该方法需要一个起始迭代器和一个结束迭代器，并会按升序排列该范围内的元素。

我们可以使用以下两个版本：

sort(starting_iterator, ending_iterator)：按升序排列由迭代器定义的范围
sort(starting_iterator, ending_iterator, comparing_function)：根据作为第三个参数给出的函数，对由迭代器定义的范围进行排序

vector<int> numbers = {3, 5, 1, 2, 4};

sort(numbers.begin(), numbers.end());

for(auto i = numbers.begin(); i != numbers.end(); i++)
	cout << *i << " ";

Output:
1 2 3 4 5

从上面的代码可以看出，sort() 方法按升序对向量进行了排序。

bool compare(int a, int b)
{
	return a > b; // 如果 a 大于 b，就返回 1
}

int main()
{
	vector<int> numbers = {3, 5, 1, 2, 4};
	
	sort(numbers.begin(), numbers.end(), compare);
	
	for(auto i = numbers.begin(); i != numbers.end(); i++)
		cout << *i << " ";

Output:
5 4 3 2 1

你可以看到，我们使用了 sort 方法的第二个版本。我们创建了 compare() 函数，使它在 a 大于 b 时返回 true。这样就能按降序对向量进行排序。

`is_sorted` 方法

STL 的 is_sorted() 方法是一个函数。如果给定范围已排序，则返回 true；否则返回 false。

is_sorted() 方法也有两个版本，和 sort() 方法完全一样：

is_sorted(starting_iterator, ending_iterator)：检查由两个迭代器定义的范围是否按升序排列。如果是，返回 true；否则返回 false
is_sorted(starting_iterator, ending_iterator, comparing_function)：根据比较函数，检查由两个迭代器定义的范围是否已排序。

vector<int> numbers = {3, 5, 1, 2, 4};

cout << is_sorted(numbers.begin(), numbers.end()) << endl;

sort(numbers.begin(), numbers.end());

cout << is_sorted(numbers.begin(), numbers.end());

Output:
0
1

bool compare(int a, int b)
{
	return a > b; // 如果 a 大于 b，就返回 1
}

int main()
{
	vector<int> numbers = {3, 5, 1, 2, 4};
	
	cout << is_sorted(numbers.begin(), numbers.end(), compare) << endl;
	
	sort(numbers.begin(), numbers.end(), compare);
	
	cout << is_sorted(numbers.begin(), numbers.end(), compare);

Output:
0
1

`partial_sort` 方法

parital_sort() 方法会对给定范围内前半部分的元素进行排序，并保持后半部分元素的初始顺序不变。
它也有两个版本：

partial_sort(start, middle, end)：对从 start 到 end 的范围进行排序，使从起始迭代器到 middle 迭代器的元素按升序排列，并保持从 middle 迭代器到结束迭代器的元素初始顺序不变
partial_sort(start, middle, end, compare)：对从 start 到 end 的范围进行排序，使从 start 到 middle 的元素根据比较函数排序，并保持从 middle 到 end 的元素初始顺序不变

vector<int> numbers = {3, 5, 1, 2, 4, 10, 7};

partial_sort(numbers.begin(), numbers.begin() + 4, numbers.end());

for(auto i = numbers.begin(); i != numbers.end(); i++)
		cout << *i << " ";

Output:
1 2 3 4 5 10 7

bool compare(int a, int b)
{
	return a > b; // 如果 a 大于 b，就返回 1
}

int main()
{
	vector<int> numbers = {3, 5, 1, 2, 4, 10, 7};
	
	partial_sort(numbers.begin(), numbers.begin() + 3, numbers.end(), compare);
	
	for(auto i = numbers.begin(); i != numbers.end(); i++)
		cout << *i << " ";

Output:
10 7 5 1 2 3 4

你可以看到，partial_sort() 方法的工作方式稍有不同，不过不用在意这一点，因为你很少会使用部分排序。

现在，记住什么是排序，记住如何正确使用 sort() 和 is_sorted() 方法，并练习使用它们。

挑战

中等

给定一个从输入中读取的数字 N。下一行有 N 个数字。先按升序输出这些数字，然后按降序输出，并用单个空格分隔。

Input
3
5 15 10

Output
5 10 15 15 10 5

亲手试试

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

using namespace std;

// Enter your code here

int main()
{
    // Enter your code here

    return 0;
}