5.3 排序

在上述的「二分」算法当中，我们利用了给定数据的某种性质，从而减少了算法的时间复杂度。显然，排序可以使得数组元素有序，从而使我们可以设计基于这个有序性的算法。在用「贪心」方法解决问题时，经常会使用到排序。

5.3.1 库函数sort()

C++ 提供了极为强力的排序函数，只需引入 algorithm 头文件即可调用。

// 以int a[n]为例，n为数组长度
sort(a, a + n);                    // 默认升序
sort(a, a + n, greater<int>());    // 降序

这个排序在不传入第三个参数的情况下，默认为 less<>()，使用元素数据类型的 < 小于号运算进行比较，使结果按升序排列。它支持所有支持比较的数据类型，包括 string，pair<>（规则为先比较 first 元素，再比较 second 元素）容器。如果要支持你自建的数据类型，或是，你需要指定排序的规则，则需要第三个参数，一般命名为 cmp。

bool cmp(int x ,int y) {
    return x < y;            //从小到大排序，把 < 换成 > 就是从大到小 
}
//...
sort(a, a + n, cmp);

在 C++11 及以后，你可以方便地使用 lambda 表达式作匿名函数定义比较规则：

sort(a, a + n, [](const auto& u, const auto& v) {
    return u < v;
});

另外，你也可以重载结构体的小于号运算符，定义该结构体的排序规则。使用map、priority_queue 这种需要比较操作的容器存储结构体，必须重载结构体的小于号运算符。

struct Node {
    int x, y;
    bool operator<(const Node& rhs) const {
        return x == rhs.x ? y < rhs.y : x < rhs.x;
    }
};

时间复杂度：#card=math&code=O%28n%5Clog%20n%29&id=jfdZc)， 为元素个数。

扩展：在面向对象的 C++ 程序设计中，cmp 的标准写法是写成「函数对象」。

struct cmp {
    bool operator ()(const int a , const int b) {
        return a < b;
    }
};

例题：力扣 451. 根据字符出现频率排序

给定一个字符串，请将字符串里的字符按照出现的频率降序排列。

示例 1: 输入: “tree”

输出: “eert”

解释: ‘e’出现两次，’r’和’t’都只出现一次。 因此’e’必须出现在’r’和’t’之前。此外，”eetr”也是一个有效的答案。

示例 2: 输入: “cccaaa”

输出: “cccaaa”

解释: ‘c’和’a’都出现三次。此外，”aaaccc”也是有效的答案。 注意”cacaca”是不正确的，因为相同的字母必须放在一起。

示例 3: 输入: “Aabb”

输出: “bbAa”

解释: 此外，”bbaA”也是一个有效的答案，但”Aabb”是不正确的。 注意’A’和’a’被认为是两种不同的字符。

原创题解：C++ 简明，按题意操作

参考代码

class Solution {
public:
    string frequencySort(string s) {
        int freq[256] = {0};
        for (char& c : s) {
            ++freq[c];
        }
        sort(s.begin(), s.end(), [](const char& u, const char& v) {
            return freq[u] == freq[v] ? u < v : freq[u] > freq[v];
        });
        return s;
    }
};

C++ 提供的 string 也是优美的 STL 容器之一，你完全可以把它当成一个数组。要「按指定规则排序」的话，就指定规则，就是这么简单。

这个例题想说明的是，排序规则可以不仅仅是变量的比较，它可以是任何能计算出布尔值的表达式。

代码中 freq[] 是数组实现的一个字符集上的哈希表，存储字符出现的频率，书写十分方便。

5.3.2 归并排序 *

归并排序可以用来找「逆序对」，简单来说就是数组中非有序的数的对数。

归并排序也是高效的排序算法，但是需要使用额外的存储空间，体现为 temp[]数组。有关归并排序，属于数据结构学习范围，本文主要面向实用竞赛，此处不作详解，模板如下：

// 归并排序
#include <iostream>
using namespace std;
const int N = 1e5 + 4;
int a[N];
int t[N];   // temp[]
int n;
// l 为起始下标， r 为最后一个元素下标
void merge_sort(int a[], int t[], int l, int r) {
    if (l >= r) {
        return;
    }
    // 递归
    int mid = l + r >> 1;
    merge_sort(a, t, l, mid);
    merge_sort(a, t, mid + 1, r);
    // 合并
    int k = 0;      // t[k]
    int i = l, j = mid + 1;
    while (i <= mid && j <= r) {
        t[k++] = a[i] < a[j] ? a[i++] : a[j++];
    }
    while (i <= mid) t[k++] = a[i++];
    while (j <= r) t[k++] = a[j++];
    for (int i=0; i<k; ++i) {
        a[l + i] = t[i];
    }
}
int main() {
    cin >> n;
    for (int i=0; i<n; ++i) {
        cin >> a[i];
    }
    merge_sort(a, t, 0, n - 1);
    for (int i=0; i<n; ++i) {
        cout << a[i] << ' ';
    }
    return 0;
}

在归并排序的基础上，加入一个统计变量ans，即可统计逆序对的数量。

#include <iostream>
using namespace std;
typedef long long ll;
const int N = 1e5 + 4;
int a[N];
int t[N];   // temp[]
int n;
ll ans = 0;        // 增加一个变量
void merge_sort(int a[], int t[], int l, int r) {
    if (l >= r) {
        return;
    }
    // 递归
    int mid = l + r >> 1;
    merge_sort(a, t, l, mid);
    merge_sort(a, t, mid + 1, r);
    // 和并
    int k = 0;      // t[k]
    int i = l, j = mid + 1;
    while (i <= mid && j <= r) {
        if (a[i] <= a[j]) {
            t[k++] = a[i++];
        } else {
            t[k++] = a[j++];
            ans += mid - i + 1;        // 增加一条更新变量语句
        }
    }
    while (i <= mid) t[k++] = a[i++];
    while (j <= r) t[k++] = a[j++];
    for (int i=0; i<k; ++i) {
        a[l + i] = t[i];
    }
}
int main() {
    cin >> n;
    for (int i=0; i<n; ++i) {
        cin >> a[i];
    }
    merge_sort(a, t, 0, n - 1);
    cout << ans << endl;
    return 0;
}

时间复杂度：#card=math&code=O%28n%5Clog%20n%29&id=UqSQy)

5.3.3 不完全的排序 *

有时候我们并不需要所有元素完全有序，一些不完全的排序算法可以优化执行效率。这里介绍两个库函数。

[partial_sort()](https://www.apiref.com/cpp-zh/cpp/algorithm/partial_sort.html)

partial_sort(a, a + i, a + n);
partial_sort(a, a + i, a + n, cmp);

使前 个元素为整个数组中最小的 个元素的有序排列。

[nth_element()](https://www.apiref.com/cpp-zh/cpp/algorithm/nth_element.html)

nth_element(a, a + k, a + n);
nth_element(a, a + k, a + n, cmp);

使第 个元素为整个数组第 小的元素，这个元素之前的元素都小于它，之后的元素都大于它。也称「快速选择算法」。
时间复杂度：#card=math&code=O%28n%29&id=N7T0A)