sort函数

C++中的sort()函数是一种通用排序算法，它提供了对序列中的元素进行排序的功能。sort()函数是C++标准库algorithm头文件中的一个函数。

sort函数的基本用法

sort()函数的函数原型如下：

sort(iterator first, iterator last);

• first和last是随机访问迭代器，它们分别指向待排序序列的起始位置和结束位置（注意，last是指向序列末尾元素的下一个位置，不包含在排序范围内）。

• sort()函数的默认行为是对序列中的元素进行升序排序。它使用序列中元素的 < 操作符来确定元素的排序顺序。

下面是一个简单的示例，对vector进行升序排序：

vector<int> nums = {5, 3, 1, 4, 2};
sort(nums.begin(), nums.end());

sort函数的自定义比较函数

如果要使用自定义的比较函数或者使用C++11中的lambda表达式进行排序，可以将比较函数或lambda表达式作为sort()的第三个参数传递。比较函数或lambda表达式应该接受两个参数并返回一个布尔值，表示第一个参数是否应该在排序中位于第二个参数之前。

这是sort()的自定义比较函数的函数原型：

sort(iterator first, iterator last, Compare comp);

• 其中，Compare是一个可调用对象（如函数指针、函数对象或lambda表达式），它接受两个元素并返回一个布尔值。

下面是sort()函数的示例，对vector进行降序排序（使用自定义比较函数）：

bool cmp(int a, int b) {return a > b;
}
vector<int> nums = {5, 3, 1, 4, 2};
sort(nums.begin(), nums.end(), cmp);//这里直接给出自比较函数的名称即可，不用给出参数

使用lambda表达式

对vector进行降序排序（使用lambda表达式）：

vector<int> nums = {5, 3, 1, 4, 2};
sort(nums.begin(), nums.end(), [](int a, int b) { return a > b; });

请注意，sort()函数使用快速排序（实际实现可能是introsort）作为其排序算法，因此它的平均时间复杂度O(n*log(n))，其中n是待排序序列的元素数量。在大多数情况下，它的性能非常出色，但在特定情况下（例如，对几乎有序的序列进行排序），其他排序算法（如std::stable_sort）可能会表现得更好。

对于sort函数使用自比较函数还是lambda表达式各自的优缺点

• 使用lambda表达式的好处是代码更简洁，因为您无需在另一个地方定义比较函数。此外，使用lambda表达式可以更容易地捕获上下文中的变量（例如，通过值捕获或引用捕获），以便在比较函数中使用。

• 另一方面，使用单独的比较函数使得代码更具可读性，特别是当比较逻辑较为复杂时。此外，这种方法可以在其他地方重用比较函数，而无需在每个需要它的地方定义相同的lambda表达式。