卓越飞翔博客
C++ 中的排序函数是用于对数组或容器中的元素进行排序的功能函数。排序可以按升序或降序排列，可以对整型、浮点型、字符型等各种类型的数据进行排序。C++ 语言提供了多个排序函数，本文将对这些排序函数的使用方法和特点进行详细介绍。
- sort()函数
sort() 函数是 C++ STL 中最常用的排序函数之一，其功能是对数组或容器中的元素进行排列。sort() 函数的基本用法如下：
sort(begin, end);其中，begin 是数组或容器中第一个元素的地址，end 是最后一个元素的地址 + 1，因此 end 指向最后一个元素后面的空地址。sort() 函数默认按升序排序，如果需要按降序排序，则可以传入一个函数指针或 lambda 表达式作为第三个参数。
下面是一个示例代码，演示了如何使用 sort() 函数对整型数组进行排序：
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int arr[] = {5, 2, 9, 1, 4, 3, 8, 6, 7};
int n = sizeof(arr) / sizeof(arr[0]);
sort(arr, arr + n);
for (int i = 0; i < n; i++)
{
cout << arr[i] << " ";
}
return 0;
}运行上述代码结果如下：
1 2 3 4 5 6 7 8 9- stable_sort() 函数
stable_sort() 函数与 sort() 函数相似，但它保证在排序后，相同值的元素的相对位置不变。stable_sort() 函数的使用方法与 sort() 函数类似，也可以传入一个函数指针或 lambda 表达式作为第三个参数。下面是一个示例代码：
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int arr[] = {5, 2, 9, 1, 4, 3, 8, 6, 7};
int n = sizeof(arr) / sizeof(arr[0]);
stable_sort(arr, arr + n);
for (int i = 0; i < n; i++)
{
cout << arr[i] << " ";
}
return 0;
}运行上述代码结果如下：
1 2 3 4 5 6 7 8 9- partial_sort() 函数
partial_sort() 函数可以将数组或容器中的元素部分排序，即将前 k 小的元素排在数组前面（或将前 k 大的元素排在数组前面）。使用方法如下：
partial_sort(begin, middle, end);其中，begin 是数组或容器中第一个元素的地址，end 是最后一个元素的地址 + 1，而 middle 是一个指向第 k 个元素的迭代器。需要注意的是，partial_sort() 函数只保证前 k 个元素是有序的，其余元素的顺序是不确定的。下面是一个示例代码：
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int arr[] = {5, 2, 9, 1, 4, 3, 8, 6, 7};
int n = sizeof(arr) / sizeof(arr[0]);
int k = 3;
partial_sort(arr, arr + k, arr + n);
for (int i = 0; i < k; i++)
{
cout << arr[i] << " ";
}
return 0;
}运行上述代码结果如下：
1 2 3- nth_element() 函数
nth_element() 函数用于选取数组或容器中的第 k 小（或第 k 大）元素，并将其排在数组的第 k 个位置。使用方法如下：
nth_element(begin, middle, end);其中，begin 是数组或容器中第一个元素的地址，end 是最后一个元素的地址 + 1，而 middle 是一个指向第 k 个元素的迭代器。需要注意的是，nth_element() 函数只保证数组的前 k 个元素是有序的，而第 k 个元素则是未排序的。下面是一个示例代码：
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int arr[] = {5, 2, 9, 1, 4, 3, 8, 6, 7};
int n = sizeof(arr) / sizeof(arr[0]);
int k = 3;
nth_element(arr, arr + k - 1, arr + n);
cout << "第 " << k << " 小的数是：" << arr[k - 1] << endl;
return 0;
}运行上述代码结果如下：
第 3 小的数是：3- make_heap() 函数
make_heap() 函数可以将数组或容器转化为堆，即将数组中的元素按照二叉堆的规则进行排序，以支持堆操作。使用方法如下：
make_heap(begin, end);其中，begin 是数组或容器中第一个元素的地址，end 是最后一个元素的地址 + 1。下面是一个示例代码：
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int arr[] = {5, 2, 9, 1, 4, 3, 8, 6, 7};
int n = sizeof(arr) / sizeof(arr[0]);
make_heap(arr, arr + n);
for (int i = 0; i < n; i++)
{
cout << arr[i] << " ";
}
return 0;
}运行上述代码结果如下：
9 7 8 6 4 3 5 1 2- push_heap() 函数
push_heap() 函数可以将一个新元素插入到堆中，并重新调整堆的结构，以满足堆的性质。使用方法如下：
push_heap(begin, end);其中，begin 是数组或容器中第一个元素的地址，end 是最后一个元素的地址。需要注意的是，被插入的新元素应当放在堆的最后一个位置。下面是一个示例代码：
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int arr[] = {5, 2, 9, 1, 4, 3, 8, 6, 7};
int n = sizeof(arr) / sizeof(arr[0]);
make_heap(arr, arr + n);
arr[n] = 0;
push_heap(arr, arr + n + 1);
for (int i = 0; i < n + 1; i++)
{
cout << arr[i] << " ";
}
return 0;
}运行上述代码结果如下：
9 7 8 6 4 3 5 1 2 0- pop_heap() 函数
pop_heap() 函数用于将堆顶元素弹出，并重新调整堆的结构，以满足堆的性质。使用方法如下：
pop_heap(begin, end);其中，begin 是数组或容器中第一个元素的地址，end 是最后一个元素的地址。需要注意的是，弹出堆顶元素后，堆的大小应当减 1。下面是一个示例代码：
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int arr[] = {5, 2, 9, 1, 4, 3, 8, 6, 7};
int n = sizeof(arr) / sizeof(arr[0]);
make_heap(arr, arr + n);
pop_heap(arr, arr + n);
n--;
for (int i = 0; i < n; i++)
{
cout << arr[i] << " ";
}
return 0;
}运行上述代码结果如下：
8 7 5 6 4 3 2 1- sort_heap() 函数
sort_heap() 函数用于将堆排序，并且保证排序后的数组是升序的。使用方法如下：
sort_heap(begin, end);其中，begin 是数组或容器中第一个元素的地址，end 是最后一个元素的地址。需要注意的是，sort_heap() 函数在对堆排序之前会先调用 pop_heap() 函数，弹出堆顶元素，因此排序后的数组大小应当减 1。下面是一个示例代码：
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int arr[] = {5, 2, 9, 1, 4, 3, 8, 6, 7};
int n = sizeof(arr) / sizeof(arr[0]);
make_heap(arr, arr + n);
sort_heap(arr, arr + n);
for (int i = 0; i < n; i++)
{
cout << arr[i] << " ";
}
return 0;
}运行上述代码结果如下：
1 2 3 4 5 6 7 8 9总结
本文详细介绍了 C++ 中常见的排序函数，包括 sort()、stable_sort()、partial_sort()、nth_element()、make_heap()、push_heap()、pop_heap() 和 sort_heap() 函数。这些排序函数各有特点，可以满足不同的排序需求。在实际编程中，根据具体情况选择适当的排序函数非常重要。
