在 C++ 标准模板库(STL) 中排序
-
在 C++ 中使用
sort()函数对数组或 STL 容器进行排序 - 在 C++ 中按降序对数组进行排序
-
使用
partial_sort()函数对数组或向量的一部分进行排序 -
使用 C++ 中的
sort()函数的用户定义或自定义排序 -
在 C++ 中使用
is_sorted()方法 - 排序算法的时间复杂度
在本教程中，我们将学习一个广泛使用的 C++ 函数，称为 sort()。我们还将查看与排序相关的其他功能。
为了在 C++ 中对数据进行排序，我们编写算法并将其应用于数据，或者我们可以使用 C++ STL 中的内置函数 sort()。sort() 函数在 algorithm 头文件中定义。
此函数使用 IntroSort 算法，这是一种混合排序算法，它使用三种排序算法，快速排序、堆排序和插入排序，以最大限度地减少运行时间。
此函数对给定范围的元素进行排序。
语法：
sort(start iterator, end iterator, compare_function)
默认情况下，这将按升序对开始迭代器和结束迭代器定义的范围内的元素进行排序（这是默认的 compare_function）。
在 C++ 中使用 sort() 函数对数组或 STL 容器进行排序
排序是对数据执行的基本操作之一。我们以递增、递减或用户定义（自定义排序）的方式排列数据。
我们可以在 C++ 中使用 sort() 函数对数组或 STL 容器（如 vector、set、map 等）进行排序。
#include <algorithm>
#include <iostream>
using namespace std;
int main() {
int arr[] = {1, 5, 8, 9, 6, 7, 3, 4, 2, 0};
// array size
int n = sizeof(arr) / sizeof(arr[0]);
vector<int> v{35, 67, 11, -9, 7, -22}; // vector
cout << "The array after sorting is : \n";
sort(arr, arr + n);
sort(v.begin(), v.end()); // sorting vector
for (int i = 0; i < n; ++i) cout << arr[i] << " ";
cout << endl;
cout << "The vector after sorting is : \n";
for (int i = 0; i < v.size(); ++i) cout << v[i] << " ";
}
输出：
The array after sorting is :
0 1 2 3 4 5 6 7 8 9
The vector after sorting is :
-22 -9 7 11 35 67
默认情况下，项目按升序排列。
在 C++ 中按降序对数组进行排序
要按降序对 C++ STL 中存在的数组或容器进行排序，我们必须在 sort() 函数中传递名为 greater<type>() 的第三个参数。此函数执行比较，以便最后的元素按降序排序。
Type 指的是我们正在使用的数组或容器的类型，int、float 或 string 类型。
#include <algorithm>
#include <iostream>
using namespace std;
int main() {
int arr[] = {1, 5, 8, 9, 6, 7, 3, 4, 2, 0};
// array size
int n = sizeof(arr) / sizeof(arr[0]);
vector<int> v{35, 67, 11, -9, 7, -22}; // vector
cout << "The array after sorting is : \n";
sort(arr, arr + n, greater<int>());
sort(v.begin(), v.end(), greater<int>()); // sorting vector
for (int i = 0; i < n; ++i) cout << arr[i] << " ";
cout << endl;
cout << "The vector after sorting is : \n";
for (int i = 0; i < v.size(); ++i) cout << v[i] << " ";
}
输出：
The array after sorting is :
9 8 7 6 5 4 3 2 1 0
The vector after sorting is :
67 35 11 7 -9 -22
使用 partial_sort() 函数对数组或向量的一部分进行排序
我们可以使用 partial_sort() 对数组的某些部分进行排序。这种方法只不过是原始排序方法的变体。
语法：
partial_sort(first, middle, last)
它重新排列范围（first，last）中的元素，以便中间之前的元素按升序排序，中间之后的元素没有任何特定顺序。
#include <algorithm>
#include <iostream>
using namespace std;
int main() {
vector<int> vr{35, 67, 11, -9, 7, -22}; // vector
cout << "The vector after partial sorting is : \n";
partial_sort(vr.begin(), vr.begin() + 2, vr.end());
for (int i = 0; i < vr.size(); ++i) cout << vr[i] << " ";
}
输出：
The vector after partial sorting is :
-22 -9 67 35 11 7
我们可以观察到只有前两个元素被排序，剩下的只是以某种随机顺序出现。
使用 C++ 中的 sort() 函数的用户定义或自定义排序
只要我们想对数据进行升序或降序排序，都可以使用这个函数，但有时我们希望数据以用户自定义的方式排序。
在这里，我们必须编写自定义排序函数，我们将作为第三个参数传递给 sort() 函数。
#include <algorithm>
#include <iostream>
using namespace std;
bool myfunction(string x, string y) { return x.size() < y.size(); }
int main() {
string str[] = {"a", "abc", "ba", "abcd"};
int n = 4;
sort(str, str + n); // normal sort function
cout << "Array after sorting : \n";
for (int i = 0; i < n; ++i) cout << str[i] << " ";
cout << endl;
sort(str, str + n, myfunction);
cout << "Array after user defined sorting : \n";
for (int i = 0; i < n; ++i) cout << str[i] << " ";
}
输出：
Array after sorting :
a abc abcd ba
Array after user defined sorting :
a ba abc abcd
第一种排序方法默认按字典升序对字符串数组进行排序。第二种排序方法根据字符串的长度对字符串进行排序，即我们在名为 myfunction 的自定义比较函数中提到的条件。
在 C++ 中使用 is_sorted() 方法
如果我们想检查给定范围的数据是否排序，我们可以使用这种方法。
#include <algorithm>
#include <iostream>
using namespace std;
int main() {
vector<int> v{35, 67, 11, -9, 7, -22}; // vector
cout << is_sorted(v.begin(), v.end());
}
输出：
0
由于向量没有排序，我们得到的输出为 0，意思是假。
排序算法的时间复杂度
sort() 的时间复杂度为 O(NlogN)，其中 N 是应用 sort() 函数的元素的数量。
