算法：常用函数

sort()

STL的排序函数sort()是最常用的函数之一，它的定义有以下两种:

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

返回值：无
复杂度： $ O(nlog_{2}n) $ .
注意。它排序的范围是[first,last),包括first，不包括last。

sort() 的比较函数

排序是对比元素的大小。sort()可以用自定义的比较函数进行排序，也可以用系统的4中函数排序，即less()、greater()、less_equal()、great_equal().在默认情况下，程序是按从小到大的顺序排序的，less()可以不写。
下面是程序的例子:

#include <bits/stdc++.h>
using namespace std;
bool my_less(int i, int j) {return i < j;} // 自定义小于
bool my_greater(int i, int j) {return i > j;} // 自定义大于

int main(){
    vector<int> a = {3,7,2,5,6,8,5,4};
    sort(a.begin(), a.begin() + 4); // 对前4个元素排序 输出 2 3 5 7 6 8 5 4
    // sort(a.begin(),a.end()); // 从小到大排序，输出 2 3 4 5 5 6 7 8
    // sort(a.begin(),a.end(),less<int>()); // 输出 2 3 4 5 5 6 7 8
    // sort(a.begin(),a.end(),myless); // 自定义排序,输出 2 3 4 5 5 6 7 8 
    // sort(a.begin(),a.end(),greater<int>()); // 从大到小排序，输出 8 7 6 5 5 4 3 2
    // sort(a.begin(),a.end(),mygreater); // 自定义排序,输出 8 7 6 5 5 4 3 2
    for(int i = 0; i < a.size(); i++) cout << a[i] << " ";
    return 0;
}

sort()还可以对结构变量进行排序，例如：

struct Student{
    char name[256];
    int score;
}
bool compare(struct Student * a, struct Student * b){
    return a -> score > b ->score;
}
······
vector <struct Student *> list;  // 定义list，把学生信息存到list里
······
sort(list.begin(),list.end(),compare); // 按分数排序

next_permutation()

STL提供求下一个排列组合的函数next_permutation()。例如3个字符a、b、c组成的序列，next_permutation()能按字典序返回6个组合，即abc、acb、bac、bca、cab、cba。
函数next_permutation()的定义有下面两种形式:

bool next_permutation(BidirectionalIterator first, BidirectionalIterator last);
bool next_permutation(BidirectionalIterator first, BidirectionalIterator last, Compare comp);

返回值：如果没有下一个排列组合，返回false，否则返回true。每执行next_permutation()一次，就会把新的排列放到原来的空间里。
复杂度: O(n)
注意，它排列的范围[first,last),包括first,不包括last。
在使用next_permutation()的时候，初始序列一般是一个字典序最小的序列，如果不是，可以用sort()排序，得到最小序列，然后再使用next_permutation().

例子

给定n个数字，从1到n，要求输出第m小的序列。
输入：数字n和m，1< n < 1000, 1 < m < 1000
输出：输出第m小的序列。

程序的思路是首先生产一个123···n的最小字典序列，即初始序列，然后用next_permutation()一个一个地生成下一个字典序更大的序列。

#include <bits/stdc++.h>
using namespace std;
int a[1001];
int main(){
    int n,m;
    while (cin>>n>>m){
        for(int i = 1; i<=n;i++) a[i] = i; // 生成一个字典序列最小的序列
        int b =1;
        do{
            if(b==m) break;
            b++;
        }while(next_permutation(a+1,a+n+1));
        for(int i=1;i<n;i++){
            cout<<a[i]<<" ";
        }
        cout<<a[n]<<endl;
    }
    return 0;
}

常用函数

sort()

sort() 的比较函数

相关函数

next_permutation()

例子

相关函数