c++ STL排序算法的使用

使用STL算法模板中的排序算法
要使用STL的算法模板，首先要包含头文件
#include <algorithm>

对于一个整数数组，一个简单的排序程序如下，

#include <iostream>
#include <algorithm>
using namespace std;
int main() {
    int a[]={3,6,1,2,4,7,1,5};
    for(auto it:a) cout<<it<<' ';
    cout<<endl;

  //第一个参数表示数组头元素的地址
  //第二个参数表示数组末尾元素指针的下一个指针
    sort(a,a+8);
    for(auto it:a) cout<<it<<' ';
}

运行结果：

3 6 1 2 4 7 1 5
1 1 2 3 4 5 6 7

其实，sort函数中的两个参数不一定非要为数组的头指针与尾指针的下一个指针，它排序排的实际上只是这两个指针之间的所有元素(包括第一个指针元素，但不包括第二个指针元素)。理解了这个，就可以仅对数组中的部分元素进行排序。

通用排序

其实，在上述代码中，sort函数可填入第三个参数，第三个参数应当填入函数指针，该函数指针所指向的函数定义应当为bool (*cmp)(T a,T b)，其中T为待排序的元素类型。sort函数排序完成后，所有相邻元素之间均应当满足该函数指针所指向函数的判断。
即，对于排序范围内的任意相邻元素，只要不满足
cmp(a[i],a[i+1])==true
两元素就交换位置。

上述例子中，可将数字类型的数组由低到高排序。如果想要由高到低排序，可使用以下代码：

#include <iostream>
#include <algorithm>
using namespace std;
bool cmp(int x,int y){
    return x>y;
}
int main() {
    int a[]={3,6,1,2,4,7,1,5};
    for(auto it:a) cout<<it<<' ';
    cout<<endl;
    sort(a,a+8,cmp);
    for(auto it:a) cout<<it<<' ';
}

如上代码执行完毕后，数组a的相邻元素之间均满足前者大于等于后者。
运行结果：

3 6 1 2 4 7 1 5
7 6 5 4 3 2 1 1

PS：

一般地，若待排序元素中不存在相等的元素，则sort函数排序完毕后，两相邻元素分别代入cmp函数必定返回true。
若待排序元素中存在相等元素，则排序完毕后一般将相互相邻。

匿名函数在sort中的应用

匿名函数的应用，在上述例子中，cmp函数仅仅只作为sort排序函数的一个参数使用，而并不由用户主动调用，将整个定义排序规则定义为全局函数显然大多数人会感到不爽，而匿名函数(lambda表达式)就解决了这个问题。
匿名函数的定义格式如下，

[待捕获的外部变量](参数定义){
    函数体
}

该lambda表达式本身的数据类型应当是一个函数指针。

对于上述由高到低排序代码的匿名排序函数可写作，

[](int x,int y){
    return x>y;
}

即完整代码如下，一下代码可实现同等效果的由高到低的排序

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

int main() {
    int a[]={3,6,1,2,4,7,1,5};
    for(auto it:a) cout<<it<<' ';
    cout<<endl;
    sort(a,a+8,[](int x,int y){
        return x>y;
    });
    for(auto it:a) cout<<it<<' ';
}

sort排序函数在复杂数据类型排序中的应用

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

typedef struct {
    string name;
    int score;
} Student;

//用于打印输出单个学生的函数
void printStudent(Student &s) {
    cout << s.name << ":" << s.score;
}

//用于打印一个学生结构体数组的函数
void printStudents(Student *s, int len) {
    for(int i=0;i<len;i++){
        printStudent(s[i]);
        cout << " ";
    }
}

#define N 5
int main() {
    Student students[] = { { "张三", 10 }, { "李四", 40 }, { "王五", 20 },
            { "小A", 31 }, { "小B", 26 } };
    cout<<"排序前："<<endl;
    printStudents(students,N);
    cout << endl;
    sort(students, students + N, [](Student a,Student b) {
        return a.score>b.score;
    });
    cout<<"排序后："<<endl;
    printStudents(students,N);
}

上述代码的运行结果为，

排序前：
张三:10 李四:40 王五:20 小A:31 小B:26
排序后：
李四:40 小A:31 小B:26 王五:20 张三:10

由上述的代码及运行结果可知，使用自定义的排序函数调用sort函数对数组排序可对任意数据元素之间进行排序。