1.1 快速排序

思想：分治

(1)确定分界点(中点)
(2)调整区间(≤x\leq x的放在左边，≥x\geq x的放在右边)
(3)递归处理左右两段

暴力的方法

扫描q[l−r]q[l-r]:把≤x\leq x的存到a[ ]a[\ ], 把≥x\geq x的存到b[ ]b[\ ]
把a[ ]a[\ ],b[ ]b[\ ]合并成q[ ]q[\ ]

优美的方法:双指针

两个指针一头一尾，如果左右两边都符合条件，那么往中间挪

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void quick_sort(int q[], int l, int r)
{
    if (l >= r) return;
    int i = l - 1, j = r + 1;
    int x = q[(l + r) / 2];
    while (i < j)
    {
        do i ++; while (q[i] < x);
        do j --; while (q[j] > x);
        if (i < j) swap(q[i], q[j]);
    }
    quick_sort(q, l, j);
    quick_sort(q, j + 1, r);
}

注：

(1)快速排序不是稳定的，因为相同的值的位置在经过排序后可能会改变。
(2)平均时间复杂度:O(nlogn)O(nlogn)

1.2归并排序

思想：分治

(1)确定分界点mid=(l+r)/2mid = (l + r) / 2
(2)递归排序左右两边
(3)归并：合二为一

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void merge_sort(int q[], int l, int r)
{
    if (l >= r) return;
    int mid = (l + r) / 2; // 取中点
    merge_sort(q, l, mid), merge_sort(q, mid + 1, r); // 递归排序左右两边
    int i = l, j = mid + 1, k = 0; // k用于对存到什么位置进行计数
    while(i <= mid && j <= r)
    {
        if (q[i] < q[j]) tmp[k ++] = q[i ++];
        else tmp[k ++] = q[j ++];
    }
    // 对还没存完的元素继续存
    while(i <= mid) tmp[k ++] = q[i ++];
    while(j <= r) tmp[k ++] = q[j ++];
    // 用tmp[]更新g[]
    for (i = l, j = 0; i <= r; i ++, j ++) q[i] = tmp[j];
}

注:

(1)归并排序是稳定的
(2)时间复杂度O(nlogn)O(nlogn)

应用：求逆序对的数量

给定一个长度为nn的整数数列，请你计算数列中的逆序对的数量。
逆序对的定义如下：对于数列的第ii个和第jj个元素，如果满足$ i<j $ 且 a[i]>a[j]a[i]>a[j]，则其为一个逆序对；否则不是。
注:一个长度为nn的数组的最大逆序对数量是当其递减时，其值为∑i=0n−1i=n(n−1)2\displaystyle\sum_{i=0}^{n-1} i = \displaystyle\frac{n(n-1)}{2}注意是否超过int(109)int(10^9)的范围

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
long long merge_sort(int q[], int l, int r) // 该函数能在归并排序的同时输出逆序对的数量
{
    if(l >= r) return 0;
    int mid = (l + r) / 2;
    // 返回结果 = 中点左边的逆序对数量+中点右边的逆序对数量+起点在左边、终点在右边的逆序对数量
    long long res = merge_sort(q, l, mid) + merge_sort(q, mid + 1, r);
    int i = l, j = mid + 1;
    int k = 0;
    // 起点在左边、终点在右边的逆序对数量 = 归并排序中每次出现左边大于右边时左边与终点之间的数量之和
    while (i <= mid && j <= r)
        if (q[i] <= q[j]) tmp[k ++] = q[i ++];
        else{
            tmp[k ++] = q[j ++];
            res += (mid - i + 1);
        }
    // 扫尾
    while (i <= mid) tmp[k ++] = q[i ++];
    while (j <= r) tmp[k ++] = q[j ++];
    // 物归原主
    for (int i = l, j = 0; i <= r; i ++, j ++) q[i] = tmp[j];
    
    return res;
}

1.3二分