[数据结构与算法]C++标准模板库之——sort函数

hello_{,大家好啊！好久不见啊，前段时间忙着找实习，好久没写博客啦，亿点点惭愧，哈哈哈O(∩_∩)O}

前言：在使用sort之前，我们需要对我们自定义的排序规则了解一点，这就是如果我们自定义的排序规则返回值必须为bool类型，另外，如果返回值为true就不交换两个数的值，反之就交换。
下面我们看一下今天的重点，sort函数。这个函数我相信大家只要是编程，那必然是会用到的！！！然而，虽然说会用到，但也仅会简单的使用该函数，今天我们就更深入的了解一下这个函数。我相信，这篇文章对于初学C++，或者说正处于刷题阶段的你一定会有所帮助！！！（大佬请绕路~）
我们如果使用过sort函数，那么我们应该知道使用这个函数那么肯定要包含头文件 #include <algorithm>
首先，我们先来看一下sort函数的参数吧~

//第一个sort函数
template<typename _RandomAccessIterator>
inline void sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
//第二个人sort函数
template<typename _RandomAccessIterator, typename _Compare>
inline void sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)

通过查看算法库（<algorithm>）我们可以看到里面有两个sort函数，一个是两个参数的sort，另一个是三个参数的sort函数。在我们平时的使用中，两个参数的sort函数使用的比较多，不过三个参数的sort函数我们同样应该掌握。

下面我们分别看一下~

两个参数的sort函数

使用之前，先介绍一下这两个参数的意义。这两个参数即是指你要遍历的起点和终点（前闭后开：即包括第一个不包括最后一个）
首先，我们看一下sort函数的最简单的用法，对基本数据类型进行排序~
例如：对数组vector<int> v({6,3,2,34,12,213,53})进行排序，我们可以这样使用sort函数，这种方法我相信大家都会使用

//基本数据类型测试:这里基本数据类型只是使用int来进行测试，其实使用char，float，double结果也都一样
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;
int main()
{
    vector<int> v({6, 3, 2, 34, 12, 213, 53});
    sort(v.begin(), v.end());

    system("pause");
    return 0;
}

这个排序使用很简单，这里就不再多说啦~

接着我们看完了基本数据类型的排序，我们再来看一下自定义数据类型的排序

对于自定义数据类型的排序，我们需要对< 运算符进行重载
例如：我们依据类里的数据对类进行排序
给定类为：

class A{
	A():val(0),fre(0)
	{
	}
	private:
		int val;
		int fre;
};

如果我们要想依据类里面的fre来进行排序的话，那么我们就需要对类A进行<运算符重载。如果我们不重载<运算符，我们怎么知道如何比较两个类A的值？对于两个参数的sort，我们一定是重载的小于号，注意一定是小于号，不是大于号！！！重载方式如下

class A
{
public:
    A() : val(0), fre(0)
    {
    }
    bool operator<(A &Y)
    {
        return this->fre < Y.fre;
    }
    //成员变量
    int val;
    int fre;
};

重载了小于号后，我们就可以正常的使用sort函数了，即可以像之前那样正常使用

//自定义数据类型排序
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;
class A
{
public:
    A() : val(0), fre(0)
    {
    }
    bool operator<(A &Y)
    {
        return this->fre < Y.fre;
    }
    //成员变量
    int val;
    int fre;
};
int main()
{

    vector<A> v2;
    A a;
    a.val = 1;
    a.fre = 9;
    v2.push_back(a);
    a.val = 2;
    a.fre = 1;
    v2.push_back(a);
    a.val = 8;
    a.fre = 3;
    v2.push_back(a);
    a.val = 6;
    a.fre = 9;
    v2.push_back(a);
    a.val = 7;
    a.fre = 3;
    v2.push_back(a);
    a.val = 5;
    a.fre = 2;
    v2.push_back(a);
    a.val = 3;
    a.fre = 9;
    v2.push_back(a);
    sort(v2.begin(), v2.end());

    system("pause");
    return 0;
}

不过我们重载小于号时，需要注意的就是，如果重载的返回值是true，那么在排序时就不进行交换，如果返回值是false，就进行交换。因此，我们在返回值时需要依据自己想从大到小排还是从小到大排来进行设计表达式。（例如：如果我想从小到大排列，那么返回值时我就需要返回this->fre < Y.fre ，从大到小排序则相反）（注：该类同样适用上面的函数模板）

两个参数的sort我们就先看这么多，下面我们继续看一下三个参数的sort

三个参数的sort

对于三个参数的sort，我们可以变化的方式就比较多了，我们一点点来看。
由于基本数据类型使用两个参数的sort就可以搞定，因此我们也就没必要使用第三个参数了，不过我们也可以使用看一下

使用之前，我们需要知道这个sort的三个参数是干嘛的。前两个参数和两个参数的sort意义一样，这第三个参数的作用就是相当于按照我们自定义的排序规则进行排序，这个参数可以是函数名，可以是对象名（注意区分类和对象）。

使用全局函数

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;
//使用全局函数
bool cmp(int x, int y)
{
    return x < y;
}

int main()
{

    vector<int> v({6, 3, 2, 34, 12, 213, 53});
    sort(v.begin(), v.end(), cmp);

    system("pause");
    return 0;
}

注意：在自定义cmp函数比较规则时，函数的参数必须是和数组的参数类型一致，并且函数的返回值类型为bool类型；并且，函数有且仅有两个参数！！！

使用类成员函数

如果使用类的成员函数来自定义排序规则，该成员函数必须是静态的成员函数！！！因为类的静态成员函数是所有类共用的并且不需要创建对象就可调用！！！
定义类的成员函数

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;
//使用类的成员函数
class MyCmp
{
public:
    bool cmp(int a, int b)
    {
        return a < b;
    }
};
int main()
{

    vector<int> v({6, 3, 2, 34, 12, 213, 53});
    sort(v.begin(), v.end(), MyCmp::cmp);

    system("pause");
    return 0;
}

使用对象名

使用对象名时分为两种情况，即可以使用临时对象也可以使用自己创建的持续对象名来自定义排序规则。不过使用对象名时，我们需要注意的就是我们必须要对括号（）操作符进行重载。因为这里既可以使用函数名也可以使用对象名的原因是利用了类的仿函数的思想。类的仿函数的思想即可以使类像一个函数一样使用。如果类可以像函数使用，那么必须要重载()运算符，并且该运算符的参数也必须有两个参数，该参数类型必须和数组的参数一致。

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;
//使用对象名
class MyCmp
{
public:
    bool operator()(int a, int b)
    {
        return a < b;
    }
    int val;
};
int main()
{

    vector<int> v({6, 3, 2, 34, 12, 213, 53});
    // sort(v.begin(), v.end(), MyCmp());//使用匿名对象名（也叫临时对象）
    MyCmp m;
    sort(v.begin(), v.end(), m);//使用持续对象名

    system("pause");
    return 0;
}

因为我们这里只需要临时用到对象名来对数据排序，所以sort的第三个参数使用临时对象就足够了，也就没必要为了排序创建一个对象。

使用STL提供的模板类

stl为我们提供了模板类less和greater，less表示从小到大排序，greater表示从大到小排序。使用这两个模板类其实和我们上面自定义的类其实是一样的，只是这个类内部自动为我们重载了括号运算符，我们在使用的时候只需要告诉该模板类我们需要对何种参数类型进行排序即可。

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;
//使用提供的less和greater类
int main()
{

    vector<int> v({6, 3, 2, 34, 12, 213, 53});
    sort(v.begin(), v.end(), less<int>());    //使用stl提供的less模板类：从小到大排序
    sort(v.begin(), v.end(), greater<int>()); //使用stl提供的greater模板类：从大到小排序

    system("pause");
    return 0;
}

结束语：好啦，sort的使用大概也就这么多，如果这几种方法大家都掌握，那么在以后的使用中绝对不是问题~

创作不易，欢迎各位大佬三连支持啊~ 点赞关注加收藏哦~ 如果有不足的地方，也欢迎各位大佬给小弟指出来~

以上排序案例都是经过自己手敲通过的，有需要可以自己尝试哦~

附全部源码

/*
    两个参数的sort
    template<typename _RandomAccessIterator>
    inline void sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
*/

#if 0
//基本数据类型测试:这里基本数据类型只是使用int来进行测试，其实使用char，float，double结果也都一样
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;
int main()
{

    vector<int> v({6, 3, 2, 34, 12, 213, 53});
    sort(v.begin(), v.end());

    system("pause");
    return 0;
}
#endif

#if 0
//自定义数据类型排序
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;
class A
{
public:
    A() : val(0), fre(0)
    {
    }
    bool operator<(A &Y)
    {
        return this->fre < Y.fre;
    }
    //成员变量
    int val;
    int fre;
};
int main()
{

    vector<A> v2;
    A a;
    a.val = 1;
    a.fre = 9;
    v2.push_back(a);
    a.val = 2;
    a.fre = 1;
    v2.push_back(a);
    a.val = 8;
    a.fre = 3;
    v2.push_back(a);
    a.val = 6;
    a.fre = 9;
    v2.push_back(a);
    a.val = 7;
    a.fre = 3;
    v2.push_back(a);
    a.val = 5;
    a.fre = 2;
    v2.push_back(a);
    a.val = 3;
    a.fre = 9;
    v2.push_back(a);
    sort(v2.begin(), v2.end());

    system("pause");
    return 0;
}
#endif

/*
    三个参数的sort
    template<typename _RandomAccessIterator, typename _Compare>
inline void sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
*/
#if 0
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;
//使用全局函数
bool cmp(int x, int y)
{
    return x < y;
}

int main()
{

    vector<int> v({6, 3, 2, 34, 12, 213, 53});
    sort(v.begin(), v.end(), cmp);

    system("pause");
    return 0;
}
#endif

#if 0
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;
//使用类的成员函数
class MyCmp
{
public:
    bool cmp(int a, int b)
    {
        return a < b;
    }
};
int main()
{

    vector<int> v({6, 3, 2, 34, 12, 213, 53});
    sort(v.begin(), v.end(), MyCmp::cmp);

    system("pause");
    return 0;
}
#endif

#if 0
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;
//使用对象名
class MyCmp
{
public:
    bool operator()(int a, int b)
    {
        return a < b;
    }
    int val;
};
int main()
{

    vector<int> v({6, 3, 2, 34, 12, 213, 53});
    // sort(v.begin(), v.end(), MyCmp());//使用匿名对象名（也叫临时对象）
    MyCmp m;
    sort(v.begin(), v.end(), m);//使用持续对象名

    system("pause");
    return 0;
}
#endif

#if 1
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;
//使用提供的less和greater类
int main()
{

    vector<int> v({6, 3, 2, 34, 12, 213, 53});
    sort(v.begin(), v.end(), less<int>());    //使用stl提供的less模板类：从小到大排序
    sort(v.begin(), v.end(), greater<int>()); //使用stl提供的greater模板类：从大到小排序

    system("pause");
    return 0;
}
#endif