学习信奥的学生都会学习很多种排序算法，但是，如果你在考试的时候遇到需要排序的问题时自己动手写排序算法的代码，那你就输了。在考试的时候，如果题目没有特别声明一定要自己写某种排序算法的实现代码，通常只需要使用std命名空间时的sort函数以及sort的周边函数就可以了。

很多的题目需要对数据进行排序，然后再做进一步的处理。因此，掌握标准函数里的排序函数就显得特别重要了。而且，使用std里的sort肯定比自己写的排序效率要高，尽管从其时间复杂度也是O(n*lgn)，但它采用了更加灵活的算法：在数据量大时，采用快速排序；数据量较少时又会使用插入排序；而在递归较深时，又会使用堆排序。总之，使用它，省时省力效率高！

sort函数包含在头文件中，不过信奥赛允许使用万能头文件，因此，直接使用万能头文件就行了。我们通过一个例子来看看它的基本用法：

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int arr[] = { 1, 4, 8, 9, 2, 7, 3, 5, 6, 10 };
    int n = sizeof(arr) / sizeof(arr[0]);

    sort(arr, arr + n);

    cout << "\n数组排序后: \n";
    for (int i = 0; i < n; ++i)
        cout << arr[i] << ",";

    return 0;
}
//排序后输出：1,2,3,4,5,6,7,8,9,10

sort函数的两个参数，第一个为数组的起始地址，第二个为结束地址（最后一个元素的地址加1）。代码中计算n为计算数组长度的方法，在竞赛中通常n是给定的，不需要另外计算。

如果需要做倒序的排序，我们可以使用三个参数的sort函数，其中第三个参数使用模板类greater，使用时需要将模板类型替换成实际的数据类型：

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int arr[] = { 1, 4, 8, 9, 2, 7, 3, 5, 6, 10 };
    int n = sizeof(arr) / sizeof(arr[0]);

    sort(arr, arr + n,greater<int>());

    cout << "\n数组排序后: \n";
    for (int i = 0; i < n; ++i)
        cout << arr[i] << " ";

    return 0;
}
// 输出：
// 数组排序后: 
// 10 9 8 7 6 5 4 3 2 1

对于特殊的排序，还可以自定义第三个参数对应的函数来实现。比如，我们要把数字按最低位的大小来排序（注意第三个参数的用法）：

#include <bits/stdc++.h>
using namespace std;

bool cmp(int x,int y)
{
    return x%10<=y%10;
}

int main()
{
    int arr[] = { 11, 4, 8, 9, 2, 7, 3, 5, 6, 10 };
    int n = sizeof(arr) / sizeof(arr[0]);

    sort(arr, arr + n,cmp);

    cout << "\n数组排序后: \n";
    for (int i = 0; i < n; ++i)
        cout << arr[i] << " ";

    return 0;
}
// 输出：
// 数组排序后: 
// 10 11 2 3 4 5 6 7 8 9

为什么前面是greater()，而自定义的函数cmp却不带括号呢？因为greater()创建一个函数对象function object。（不需要深究！）

除了对数据排序外，sort也可以对其它的STL数据类型进行排序（比如对vector类型），用法：

sort(vect.begin(), vect.end()); 标准模板库里的数据类型大都支持begin() 和 end().

数据排序之后，经常用到的函数有：

binary_search(), lower_bound,upper_bound

下面通过一个代码示例来讲解它们的用法：

#include <bits/stdc++.h>
using namespace std;

bool cmp(int x,int y)
{
    return x%10<=y%10;
}

int main()
{
    int arr[] = { 1, 4, 8, 9, 2, 7, 3, 5, 6, 10 };
    int n = sizeof(arr) / sizeof(arr[0]);

    sort(arr, arr + n);

    // 第一个出现 5 的地址
    auto q = lower_bound(arr, arr + n, 5);

    // 最后出现 5 的下一个地址
    auto p = upper_bound(arr, arr + n, 5);


    auto l=binary_search(arr,arr+n,5);

    for (int i = 0; i < n; ++i)
        cout << arr[i] << " ";

    cout<<endl;

    cout << "lower_bound: ";
    cout << q-arr<< endl;

    cout << "upper_bound: ";
    cout << p-arr << endl;

    cout<<"Binary search 5: "<<(l>0?"Found":"Not Found")<<endl;



    return 0;
}

lower_bound(arr, arr + n, 5) 找到第一个大于等于5的位置地址；

upper_bound(arr, arr + n, 5) 找到第一个大于5的位置地址；

binary_search(arr, arr + n, 5) 返回是否找到5.

要特别注意的是，如果数据是逆序或者特殊排序的，这三个函数也要做相应的调整（即增加一个参数）：

#include <bits/stdc++.h>
using namespace std;

bool cmp(int x,int y)
{
    return x%10<=y%10;
}

int main()
{
    int arr[] = { 1, 4, 8, 9, 2, 7, 3, 5, 6, 10 };
    int n = sizeof(arr) / sizeof(arr[0]);

    sort(arr, arr + n,greater<int>());

    // 第一个出现 5 的地址
    auto q = lower_bound(arr, arr + n, 5,greater<int>());

    // 最后出现 5 的下一个地址
    auto p = upper_bound(arr, arr + n, 5,greater<int>());


    auto l=binary_search(arr,arr+n,5,greater<int>());

    for (int i = 0; i < n; ++i)
        cout << arr[i] << " ";

    cout<<endl;

    cout << "lower_bound: ";
    cout << q-arr<< endl;

    cout << "upper_bound: ";
    cout << p-arr << endl;

    cout<<"Binary_search: "<<(l>0?"Found":"Not Found")<<endl;



    return 0;
}