在C++标准库中使用sort()函数

引言

嗨！今天我们要讨论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()
{  
    //array initialisation
    int demo[5] = {5, 4, 3, 2, 1};
    
    int len = sizeof(demo)/sizeof(demo[0]);
     
    cout<<"Before sorting array : ";
    for(int i=0; i<len; i++)
    {
        cout<<" "<<demo[i];
    }
     
    std::sort(demo, demo + len);//Sorting demo array
     
    cout<<"\n\nAfter sorting array : ";
    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()
{  
    //array initialisation
    int demo[5] = {44, 22, 55, 33, 66};
    
    int len = sizeof(demo)/sizeof(demo[0]);
     
    cout<<"Before sorting array : ";
    for(int i=0; i<len; i++)
    {
        cout<<" "<<demo[i];
    }
     
    std::sort(demo, demo + len, greater<int>());//Sorting demo array
     
    cout<<"\n\nAfter sorting array : ";
    for(int i=0; i<len; i++)
    {
        cout<<" "<<demo[i];
    }
    return 0;
}

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

#include<iostream>    
#include<algorithm>
using namespace std;
int main()
{  
    //array initialisation
    int demo[5] = {44, 22, 55, 33, 66};
    
    int len = sizeof(demo)/sizeof(demo[0]);
     
    cout<<"Before sorting array : ";
    for(int i=0; i<len; i++)
    {
        cout<<" "<<demo[i];
    }
     
    std::sort(demo, demo + len, [](int &e1, int &e2){ return e1>e2; });//Sorting demo array
     
    cout<<"\n\nAfter sorting array : ";
    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;

//our function
bool My_func( int a, int b)
{	
	return (a%10)<(b%10);
}

int main()
{  
    //array initialisation
    int demo[5] = {18, 45, 34, 92, 21};
    
    int len = sizeof(demo)/sizeof(demo[0]);
     
    cout<<"Before sorting array : ";
    for(int i=0; i<len; i++)
    {
        cout<<" "<<demo[i];
    }
     
    std::sort(demo, demo + len, My_func);//Sorting demo array
     
    cout<<"\n\nAfter sorting array : ";
    for(int i=0; i<len; i++)
    {
        cout<<" "<<demo[i];
    }
    return 0;
}

结果：

从上面的输出结果可以看出，通过我们的My_func()函数，演示数组已经成功按照(element%10)因子进行了排序。

C++中std::sort()的复杂度

sort()函数对N个元素进行排序时需要进行Nlog(N)次比较。因此，在最坏的情况下，其时间复杂度为O(Nlog(N))。

概述

这就是关于这个问题的所有内容。今天我们了解了C++标准库中sort()函数的使用和工作原理。希望你有了清楚的理解。

请注意，sort()函数也可以用于除了数组之外的其他数据结构，比如向量等等。在本教程中，我们选择了数组以便更好地理解。

我们建议您浏览我们的C++教程。

如有任何进一步的问题，请随时在下方评论区提出。

参考文献

• std::sort() – C++ Documentation,
• Standard Template Library (STL) in C++,
• – C++ algorithm Library.