基本排序

冒泡排序

每次交换相邻两项。

冒泡循环一轮结束后，总是将当前最小或最大的数移动到最前或最后，一共 4 种实现方法。

使用冒泡排序将一个数组从小到大排序时，相邻交换次数将等于数组的逆序数（参考 （链接未公开））

实现

constexpr size_t MAXN = 1e5 + 5;
int a[MAXN];

void bubble_sort(int a[], size_t n)
{
    for (size_t i = 1; i <= n - 1; i++)
    {
        for (size_t j = n - 1; j >= i; j--)
        {
            if (a[j] > a[j + 1])
            {
                swap(a[j], a[j + 1]);
            }
        }
    }
}

选择排序

每轮找出数组的第 k 小 a_l，然后将 a_k 和 a_l 交换位置，循环 k - 1 轮。

这个算法在第 k 轮总是可以保证前 k - 1 小已经排好序，所以每次求第 k 小就是求 a_k, a_{k + 1}, \dots, a_n 的第 k 小。

插入排序

特点：常数较小。当数组已经基本有序时效率很高。

最坏时间复杂度：O(n^2)

算法流程

设 a 为待排序数组，

快速排序

快速排序

两指针交替排序

三路快速排序

三路快速排序，在选定 pivot 后，将数据划分为小于、等于、大于 pivot 三段，然后对小于、大于两段递归使用快速排序，从而避免全部数据相等时复杂度退化到 O(n^2) 的情况。

思路

维护三个指针 i, p, q，i 表示当前处理元素的指针，p 表示 [0, p) 中的数据都小于 pivot，q 表示 [q, n) 中的数据都大于 pivot。算法过程中，维护数组，使 [p, i] 的数据都等于 pivot。

初始时，选择 pivot c，令 i = 0, p = 0, q = n，然后当 i < q 时反复循环：

• 若 a_i < c，则交换 a_i, a_p，然后 i, p 自增 1；
• 若 a_i > c，则 q 自减 1，然后交换 a_i, a_q；
• 若 a_i = c，则 i 自增 1。

经过以上步骤，最终 [0, p) 的数据都小于 c，[q, n) 的数据都大于 c，对两边递归排序即可。

代码

void quick_sort(int a[], size_t len)
{
    if (len <= 1) return;
    int pivot = a[rand() % len];
    size_t i = 0, p = 0, q = len;
    while (i < q)
    {
        if (a[i] < pivot)
        {
            swap(a[i], a[p]);
            i++, p++;
        }
        else if (a[i] > pivot)
        {
            q--;
            swap(a[i], a[q]);
        }
        else
        {
            i++;
        }
    }
    quick_sort(a, p);
    quick_sort(a + q, len - q);
}

使用模板编程：

template <typename It>
void quick_sort(It l, It r)
{
    static mt19937 rnd;
    if (r - l <= 1)
    {
        return;
    }
    auto pivot = *(l + rnd() % (r - l));
    It p = l, q = r, i = l;
    while (i < q)
    {
        // [l, p) < pivot
        // [p, i) = pivot
        // [i, q) to search
        // [q, r) > pivot
        if (*i < pivot)
        {
            swap(*p, *i);
            p++;
            i++;
        }
        else if (*i > pivot)
        {
            q--;
            swap(*i, *q);
        }
        else
        {
            i++;
        }
    }
    quick_sort(l, p);
    quick_sort(q, r);
}

C++ 的 std::sort

自定义比较方法

比较函数

在 std::sort 中可以通过传入一个比较函数，来自定义排序方法。C++ 的约定是，当 cmp(a, b) 返回 true 时，就会让 a 排在 b 前面。

运算符重载

对于自定义的数据结构，例如类（结构体），可以通过运算符重载的方法，通过重载小于号 < 来让 C++ 得以比较。

技巧：浮点数规避

例如，如果我们定义了一个分数类，代表分数 \frac{a}{b}：

struct Fraction {
   int a, b;
} x, y;

如果我们直接定义其比较算法为 x.a / y.a < x.b / y.b，就可能出现比较精度的问题，这时候更常见的做法是写为

bool operator<(Fraction x, Fraction y)
{
    return x.a * y.b < x.b * y.a;
}

不过这种做法可能带来超出 int 范围的问题。

这种技巧在 （链接未公开） 也会使用。

严格弱序

序关系