C++中sort和stable_sort的使用方法

掌握C排序神器：sort与stable_sort的实战秘籍

在编程的世界里，排序是一个无处不在的任务。无论是处理数据分析、优化算法，还是简单地整理用户输入，排序都扮演着至关重要的角色。C，作为一门强大且灵活的编程语言，为我们提供了多种排序工具，其中`std::sort`和`std::stable_sort`是最常用、最强大的两个。今天，我们就来揭开它们的神秘面纱，一起探索如何在C中高效、优雅地使用这两个排序函数。

一、排序的基石：std::sort

`std::sort`是C标准库中的一个函数，位于``头文件中。它能够对给定的元素范围进行排序，默认情况下使用升序排列。`std::sort`采用了高效的排序算法（通常是快速排序、堆排序或这两种算法的结合），在大多数情况下都能提供出色的性能。

使用方法

`std::sort`的基本用法非常简单，它接受三个参数：要排序的序列的开始迭代器、结束迭代器以及一个可选的比较函数。

```cpp

include

include

include

int main() {

std::vector vec = {5, 2, 9, 1, 5, 6};

// 使用默认比较函数进行升序排序

std::sort(vec.begin(), vec.end());

// 输出排序后的结果

for (int n : vec) {

std::cout << n << " ";

std::cout << std::endl;

return 0;

```

在上面的例子中，`std::sort`对`vec`进行了升序排序，并输出了排序后的结果。

自定义比较函数

如果你需要按照特定的规则进行排序，可以提供一个自定义的比较函数。比较函数应该接受两个参数，并返回一个布尔值。如果第一个参数应该在第二个参数之前，则返回`true`，否则返回`false`。

```cpp

include

include

include

// 自定义比较函数，实现降序排序

bool compareDesc(int a, int b) {

return a > b;

int main() {

std::vector vec = {5, 2, 9, 1, 5, 6};

// 使用自定义比较函数进行降序排序

std::sort(vec.begin(), vec.end(), compareDesc);

// 输出排序后的结果

for (int n : vec) {

std::cout << n << " ";

std::cout << std::endl;

return 0;

```

在这个例子中，我们定义了一个名为`compareDesc`的比较函数，用于实现降序排序。然后，我们将这个函数作为第三个参数传递给`std::sort`。

二、稳定的排序：std::stable_sort

与`std::sort`不同，`std::stable_sort`保证在排序过程中，如果两个元素相等，则它们在排序后的相对位置与排序前的相对位置相同。这种稳定性在某些场景下非常有用，比如当你需要对多个字段进行排序时（先按字段A排序，再按字段B排序），稳定性可以确保字段A的排序结果不会因字段B的排序而改变。

使用方法

`std::stable_sort`的使用方法与`std::sort`几乎完全相同，也是接受三个参数：要排序的序列的开始迭代器、结束迭代器以及一个可选的比较函数。

```cpp

include

include

include

include

// 自定义比较函数，根据字符串长度排序

bool compareLength(const std::string &a, const std::string &b) {

return a.size() < b.size();

int main() {

std::vector vec = {"apple", "banana", "cherry", "date"};

// 使用自定义比较函数进行稳定排序

std::stable_sort(vec.begin(), vec.end(), compareLength);

// 输出排序后的结果

for (const std::string &str : vec) {

std::cout << str << " ";

std::cout << std::endl;

return 0;

```

在这个例子中，我们定义了一个名为`compareLength`的比较函数，用于根据字符串的长度进行排序。然后，我们使用`std::stable_sort`对这个字符串向量进行了排序，并输出了排序后的结果。

三、性能