Sorting Methods-排序方法

资料-Resources

• 3.1 - Sorting Theory
• Sorting

Library Sorting-库排序

虽然通常你不需要了解排序算法的具体实现，但是你必须会使用内置排序方法，因为它们既高效又可靠。在 C++ 中，标准库已经提供了多种排序函数，你只需要调用即可，而不必手动实现复杂算法。

资料-Resources

• 3.2 - Sorting in C++
• std::sort
• C++ Tricks

Static Arrays-静态数组

要对静态数组进行排序，可以使用 sort(arr, arr + N)，其中 $N$ 是需要排序的元素个数。你也可以通过替换 $arr$ 和 $arr+N$ 来指定排序的子区间。例如：sort(arr + 1, arr + 4，将会排序索引区间 $[1,4)$ 的元素，即 arr[1], arr[2], arr[3]。

#include <bits/stdc++.h>
using namespace std;

int main() {
	int arr[] = {5, 1, 3, 2, 4};
	int N = 5;
	sort(arr, arr + N);
	for (int i = 0; i < N; i++) cout << arr[i] << " ";  // 1 2 3 4 5
	cout << endl;

	int arr2[] = {5, 1, 3, 2, 4};
	sort(arr2 + 1, arr2 + 4);
	for (int i = 0; i < N; i++) cout << arr2[i] << " ";  // 5 1 2 3 4
}

Dynamic Arrays-动态数组

要对动态数组（如 $vector$）进行排序，可以使用：sort(v.begin(), v.end()); 或者 sort(begin(v), end(v)); 。默认情况下，$sort$ 会将数组按升序排列。

同样，你也可以指定排序的子区间。例如：sort(v.begin() + 1, v.begin() + 4); 这将排序索引区间 $[1,4)$ 的元素，即 $v[1],v[2],v[3]$。

#include <bits/stdc++.h>
using namespace std;

int main() {
	vector<int> v{5, 1, 3, 2, 4};
	sort(v.begin(), v.end());
	// Outputs 1 2 3 4 5
	for (int i : v) { cout << i << " "; }
	cout << endl;

	v = {5, 1, 3, 2, 4};
	sort(v.begin() + 1, v.begin() + 4);
	// Outputs 5 1 2 3 4
	for (int i : v) { cout << i << " "; }
	cout << endl;
}

(Dynamic) Arrays of Pairs & Tuples-成对或元组数组排序

在 C++ 中，默认情况下：

• $pair$ 会先按照 第一个元素 $first$ 排序

• 如果第一个元素相等，则按照 第二个元素 $second$ 排序

#include <bits/stdc++.h>
using namespace std;

int main() {
	vector<pair<int, int>> v{{1, 5}, {2, 3}, {1, 2}};
	sort(v.begin(), v.end());

	/*
	 * Outputs:
	 * 1 2
	 * 1 5
	 * 2 3
	 */
	for (pair<int, int> p : v) { cout << p.first << " " << p.second << endl; }
}

在 $C++$ 中，$tuple$ 的排序规则与 pair 类似：

• 先按第一个元素排序

• 如果第一个元素相等，则按第二个元素排序

• 依次类推，按顺序比较后续元素