掌握C++标准库sort()函数：高效排序的完整教程

2 年 ago

文, 翔

2 minutes

引言

嗨！今天我们要讨论C++标准库中的sort()函数。

基础来说，排序是对物品进行系统排序的过程。这些物品可以是一个序列的元素或任何数据结构中的元素。

在C++中，标准库提供了一个预定义且可直接使用的函数sort()来执行这个排序操作。所以让我们马上开始吧。

C++ 中的 std::sort() 函数

C++中的std::sort()函数是内建函数，用于按特定顺序对任意形式的数据结构进行排序。它在algorithm头文件中被定义。sort()函数的原型如下：

void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);

这个函数没有返回任何值。它只是更新从第一个到最后一个迭代器或位置的元素/项。第三个参数（可选）comp必须是一个确定排序元素顺序的函数。当未指定时，默认按升序排序，相当于使用std::less()函数。

sort()函数使用一种名为Introsort的三层混合排序技术。它是快速排序、堆排序和插入排序的组合。

在C++中使用sort()函数对数据进行排序

既然我们已经掌握了sort()函数的基本知识，让我们在我们的C++程序中使用它来对一些数据结构（例如数组）进行排序吧。

1. 按升序排列

如前所述，如果未提及comp参数，则sort()函数默认按升序对一组项目进行排序。

所以对于下面的例子，我们仅仅传递了第一个（起始）和最后一个（结束）可迭代对象来按升序排序数组。

#include<iostream>    
#include<algorithm>
using namespace std;
int main()
{  
    //数组初始化
    int demo[5] = {5, 4, 3, 2, 1};
    
    int len = sizeof(demo)/sizeof(demo[0]);
     
    cout<<"排序前数组 : ";
    for(int i=0; i<len; i++)
    {
        cout<<" "<<demo[i];
    }
     
    std::sort(demo, demo + len);//对demo数组进行排序
     
    cout<<"\n\n排序后数组 : ";
    for(int i=0; i<len; i++)
    {
        cout<<" "<<demo[i];
    }
    return 0;
}

输出结果：

在这里，demo是给定数组的第一个元素的地址，(demo + len)是给定数组最后一个元素的地址。因此，假设comp函数默认为std::less()函数，sort()函数将按照升序对数组进行排序。

注意：std::less() 函数比较两个参数，并根据第一个参数是否小于第二个参数返回 true 或 false。

2. 按降序排序

我们还可以通过操作第三个参数，使用sort()函数对数据结构进行降序排序。让我们看看如何操作。

在下面的代码中，我们使用了std::greater()函数，它的功能与std::less()函数完全相反。它比较两个参数并在第一个参数大于另一个参数时返回true，否则返回false。

#include<iostream>    
#include<algorithm>
using namespace std;
int main()
{  
    // 数组初始化
    int demo[5] = {44, 22, 55, 33, 66};
    
    int len = sizeof(demo)/sizeof(demo[0]);
     
    cout<<"排序前的数组：";
    for(int i=0; i<len; i++)
    {
        cout<<" "<<demo[i];
    }
     
    std::sort(demo, demo + len, greater<int>());// 对demo数组进行排序
     
    cout<<"\n\n排序后的数组：";
    for(int i=0; i<len; i++)
    {
        cout<<" "<<demo[i];
    }
    return 0;
}

如下所示，我们还可以将lambda函数作为sort()函数的第三个参数使用。

#include<iostream>    
#include<algorithm>
using namespace std;
int main()
{  
    // 数组初始化
    int demo[5] = {44, 22, 55, 33, 66};
    
    int len = sizeof(demo)/sizeof(demo[0]);
     
    cout<<"排序前的数组：";
    for(int i=0; i<len; i++)
    {
        cout<<" "<<demo[i];
    }
     
    std::sort(demo, demo + len, [](int &e1, int &e2){ return e1>e2; });// 对demo数组进行排序
     
    cout<<"\n\n排序后的数组：";
    for(int i=0; i<len; i++)
    {
        cout<<" "<<demo[i];
    }
    return 0;
}

上述两个例子生成的输出与下方给出的相同。并且成功地按降序排列了演示数组。

3. 使用用户自定义的顺序进行排序

std::sort()函数的第三个参数（comp）也可以是一个用户自定义函数，用于定义排序的顺序。

需要注意的是，这个函数必须返回一个布尔值（True/False）。

例如，在以下代码片段中，我们尝试根据它们被10除时产生的余数（使用’%’运算符）对数组的元素进行排序。

#include<iostream>
#include<algorithm>
using namespace std;

//我们的自定义函数
bool My_func( int a, int b)
{	
	return (a%10)<(b%10);
}

int main()
{  
    //数组初始化
    int demo[5] = {18, 45, 34, 92, 21};
    
    int len = sizeof(demo)/sizeof(demo[0]);
     
    cout<<"排序前的数组：";
    for(int i=0; i<len; i++)
    {
        cout<<" "<<demo[i];
    }
     
    std::sort(demo, demo + len, My_func);//对demo数组进行排序
     
    cout<<"\n\n排序后的数组：";
    for(int i=0; i<len; i++)
    {
        cout<<" "<<demo[i];
    }
    return 0;
}

运行结果：

从上述输出结果可以清晰地看到，通过我们自定义的My_func()函数，演示数组已成功按照元素对10取模(element%10)的规则进行了排序。

C++中std::sort()的时间复杂度分析

std::sort()函数在对N个元素进行排序时，平均需要进行Nlog(N)次比较操作。因此，在最坏的情况下，其时间复杂度为O(Nlog(N))，这使得C++标准库中的sort()函数成为处理大规模数据排序的高效选择。

总结与扩展

通过本教程，我们全面了解了C++标准库中sort()函数的使用方法和工作原理。希望这些内容能够帮助您清楚地理解如何在实际编程中应用这一强大的排序工具。

值得注意的是，sort()函数不仅适用于数组，还可以用于其他STL容器，如向量(vector)、列表(list)等数据结构。在本教程中，我们选择数组作为示例主要是为了便于初学者更好地理解排序的基本概念。

如果您想深入学习更多C++编程知识，我们建议您继续浏览我们的C++教程系列，那里有更多关于标准模板库(STL)和其他高级主题的详细讲解。

如有任何疑问或需要进一步说明，欢迎在下方评论区留言，我们将尽快为您解答。

参考文献

std::sort() – C++官方文档
C++标准模板库(STL)详解
C++算法库参考手册

#C++ sort函数 #C++ 教程 #C++ 标准库 #STL #排序算法