acwing算法笔记-快速排序+归并排序

快速排序

快速排序的主要思想是基于分治的，分治算法的核心是递归。那么对于一个分治问题，我们可以有以下三步。

  1. 分成子问题
  2. 递归处理子问题
  3. 子问题合并

现在我们来看总结好的快排算法模板。

  1. 确定分界点 分界点取的是数值而不是索引，可以在区间[l,r]内任意取值，例如左侧q[l]，右侧q[r]，中间q[(l+r)/2]，随机q[random]都可以。
  2. 调整区间 把整个区间一分为二，满足以下性质，即让左边所有的数都<=x,右边所有的数都>=x。
  3. 递归地处理左右两段

其中1，2主要是完成分治中的第一步分成子问题，3是完成分治中的第二步递归处理子问题，快排这里不需要子问题合并，因为它是in-place算法。


785. 快速排序

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <iostream>

using namespace std;

const int N = 100010;

int q[N];

void quick_sort(int q[], int l, int r)
{
    //递归边界
    if (l >= r) return;

    //确定分界点
    int i = l - 1, j = r + 1, x = q[l + r >> 1];

    //调整区间
    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);
}

int main()
{
    int n;
    scanf("%d", &n);

    for (int i = 0; i < n; i ++ ) scanf("%d", &q[i]);

    quick_sort(q, 0, n - 1);

    for (int i = 0; i < n; i ++ ) printf("%d ", q[i]);

    return 0;
}

边界情况分析

快排算法的边界情况很多，建议直接背一个模板。如果自己修改完之后发现错了，建议手动模拟错误数据的执行过程，就会发现问题所在了。

根据上文提供的题解，我们来对于其中的一些片段进行边界分析。

  1. 递归边界
    if (l >= r) 这里也可以写成 l == r，因为最多就是l == r的时候就会终止，写成l >= r 只是习惯问题。

  2. 为什么写成do while，而不是while
    由于使用do-while循环,所以i和j一定会变化,使得循环会继续下去,但是如果采用while循环,i和j在特殊情况下（q[i] = q[j] = x),i和j都不会更新,导致while 陷入死循环。

  3. do while里，能否写成q[i]<=x, q[j]>=x
    不可以！ 乍一看好像很有道理，满足了两边的性质，但是这里存在边界问题，为了更直观的分析，这里我们举一个例子。

    比如这组数据：
    10
    49 59 88 37 98 97 68 54 31 3

    第一轮选中的是98（它也是最大的），然后do i++; while (q[i] <= x);
    整个数组全部都跳过去了，i指针开始越界访问（但是在C++里不一定会报错，因为C语言对于数组引用不进行任何边界检查，除非越界访问到了不可读的内存地址）如果不报错，并且如果之后的q[i] <= x (此时i > r) 条件也不幸成立，就会造成一直循环下去，造成内存超限(Memory Limit Exceeded)循环一直不会退出。

  4. if(i < j) swap(q[i], q[j])能否使用 i <= j，或者不需要条件
    首先考虑能否不需要条件，假设i和j在倒数第二次循环的时候已经相邻，进入最后一次while循环，因为会先执行i++，j–,所以此时i和j已经错位即i>j，交换后不满足分区间的性质了。

    那么是否可以加上==呢，这个是可以的，因为 i = j 时，交换一下q[i],q[j] 无影响，之后也会立马跳出循环。

  5. 递归处理左右两段时的边界问题
    这一块是比较棘手的地方，在这里我们详细论述一下。

    首先上结论，最后一句可以写成两种形式

    1
    2
    3
    4
    5
    6
    7
    // Solution1 此时x一定不能取到q[r]
    quick_sort(q, l, j);
    quick_sort(q, j + 1, r);

    //Solution2 此时x一定不能取到q[l]
    quick_sort(q, l, i - 1);
    quick_sort(q, i, r);

    1.为什么不可以写成quick_sort(q, l, j-1), quick_sort(q, j, r)orquick_sort(q, l, i), quick_sort(q, i + 1, r)
    这里首先我们考虑最后一轮循环，最后一轮循环有点特殊即最后一轮循环的if语句一定不会执行，因为最后一轮循环一定满足 i >= j,不然不会跳出while循环的，所以if语句一定不执行。

    由于if语句不执行，最后没有进行swap交换，那么跳出循环后，只能保证i >= j, q[l..i-1] <= x, q[i] >= x,和q[j+1..r] >= x, q[j] <= x。

    对于这种写法quick_sort(q, l j-1), quick_sort(q, j, r),q[l..j-1] <= x是显然成立的，但quick_sort(q, j, r)中的q[j] 却是 q[j] <= x，这不符合快排区间性质的要求。

    同理对于这种写法quick_sort(q, l i), quick_sort(q, i + 1, r),q[i + 1..r] >= x是显然成立的，但quick_sort(q, l, i)中的q[i] 却是 q[i] >= x，这不符合快排区间性质的要求。

    那么为了方便不让自己写错，我们一定要严格按照循环不变式对应的分段写，[l, i - 1]的数都<=x, l[j+1, r]的数都>=x，所以我们可以用i-1或者j+1。

    2.为什么以j划分，x就不能取到q[r], 以i划分，x就不能取到q[l]
    当 x = q[r],j指针首次移动到r后，因为不满足q[j] > x,所以停留在原地，直到下一次循环才可以移动，此时j = r quick_sort(q, l ,j) => quick_sort(q, l, r), 这就跟进入递归时一样了,导致死循环,一直无限划分[l, r]，无法进入下一个while循环。

    同理当 x = q[l],i指针首次移动到l后，因为不满足q[i] < x,所以停留在原地，直到下一次循环才可以移动，此时i = l quick_sort(q, i ,r) => quick_sort(q, l, r), 这就跟进入递归时一样了,导致死循环,一直无限划分[l, r],无法进入下一个while循环。

    这里总结一个判断的技巧，无论是以j还是i划分，一定不能出现sort[l, r]，而x = q[position]就会导致肯定在某一次while循环中，指针会最终停留在position，这样跳出while循环后，就会得到sort(l, postion)或者sort(postion, r)

    以上所有的停留指的是一次while循环结束后，指针最终所在的位置。

    简化思路: sort[q, l, j], 不能出现sort[l, r], 所以j指针不能停留在r，所以x不能取到q[r]。同理对于其他的划分也可以应用一样的思路。

    3. x=q[l+r>>1], x=q[l+r+1>>1]的边界问题
    x=q[l+r>>1]此时x取的是序列中间靠左的位置(如果序列个数为奇,则取正中间,如果为偶,则取中间靠左),此时如果元素个数为2,则中间靠左就是第1个元素,这时就跟x=q[l]的边界情况一致了，所以就直接看成q[l]去思考边界。

    x=q[l+r+1>>1]此时x取的是序列中间靠右的位置(如果序列个数为奇,则取正中间,如果为偶,则取中间靠右),此时如果元素个数为2,则中间靠右就是第2个元素,这时就跟x=q[r]的边界情况一致了，所以就直接看成q[r]去思考边界。


算法分析

空间复杂度：
快速排序是原地算法，不需要额外的空间来存储元素，但是由于快排是递归调用，所以会消耗函数调用栈空间，每次函数调用中只使用了常数的空间。

最好情况：每次左右都是均匀划分，递归树的深度为：logn，嵌套递归调用logn次，其空间复杂度也就为 O(logn)。

最坏情况：每次只能排除一个元素，要递归剩下n-1个元素，如：[1,2,3,4,5]，或[5,4,3,2,1]
需要进行n‐1次递归调用，其空间复杂度为O(n)。

平均情况：空间复杂度也为O(logn)。

时间复杂度：
考虑到最好情况，每次都是均匀划分，划分操作的时间复杂度为O(n),可以得到时间：
T(n) =2 * T(n/2) + O(n)
应用主方法或者递归树，都可以求解复杂度为O(nlogn)。

但如果是最坏情况，待排序的序列为正序或者逆序，每次划分只得到一个比上一次划分少一个记录的子序列，那么计算的成本就变为了：
T(n) = T(n-1) + O(n)
容易求解复杂度为O(n2)

事实上只要划分是常数比例的，算法的运行时间总是O(nlgn)。 假设按照 9:1 划分，每层代价最多为 cn, 递归深度为 log10/9 n=Θ(lgn)，故排序的总代价为O(nlgn)

稳定性：
首先，排序算法的稳定性通俗地讲就是能保证排序前2个相等的数其在序列的前后位置顺序要和排序后它们两个的前后位置顺序相同。

简单形式化一下，如果Ai = Aj, Ai原来在位置前，排序后Ai还是要在Aj位置前。

而快速排序无法保证相等的元素的相对位置不变，因此它是不稳定的排序算法。


786. 第k个数

基本思路

快排需要对原数组排序，而这里只需要找到第k个数，所以可以利用二分的思想，让时间复杂度继续降低
和快排的唯一区别就是不需要递归处理左右两边，只需要递归处理答案所在的那边就行。

时间复杂度：$O(n)$
空间复杂度：$O(logn)$

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <iostream>

using namespace std;

const int N = 1e5 + 10;

int n, k, q[N];

int quick_select(int l, int r, int k) {
    // 前半部分和快排完全相同
    if (l >= r) return q[l];
    
    int i = l - 1, j = r + 1, x = q[l + r >> 1];
    
    while (i < j) {
        do i++; while (q[i] < x);
        do j--; while (q[j] > x);
        if (i < j) swap(q[i], q[j]);
    }
    
    // l - j 有 j-l+1个数字
    int sl = j - l + 1;
    if (k <= sl) quick_select(l, j, k);
    else quick_select(j + 1, r, k - sl);
}

int main() {
    cin >> n >> k;
    
    for (int i = 0; i < n; i++) cin >> q[i];

    cout << quick_select(0, n - 1, k);
}

tip: 这里数组定义是全局变量，所以可以不需要传参，快速排序那道题也是同理，但是如果数组是局部变量，就需要通过函数传参了。


Reference

[1]. yxc
[2]. Protein 第k个数（纯手写）
[3]. Bug-Free


归并排序

归并排序同样也是分治算法，所以也有以下三个步骤。

  1. 分成子问题
  2. 递归处理子问题
  3. 子问题合并

现在我们来看总结好的归并排序的算法模板。

  1. 确定分界点 分界点取的中点，这里是索引，而不是数值了。
  2. 递归排序左右两段
  3. 归并合二为一 把排序好的左右两段合成有序的一段

其中1是分治中的第一步分成子问题，2是完成分治中的第二步递归处理子问题，3就是子问题合并，显然归并排序不是in-place算法，需要额外的空间。


787. 归并排序

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <iostream>

using namespace std;

const int N = 1e5 + 10;

int a[N], tmp[N];

void merge_sort(int q[], int l, int r)
{
    //递归边界
    if (l >= r) return;

    //确定分界点
    int mid = l + r >> 1;

    //递归排序左右两段
    merge_sort(q, l, mid), merge_sort(q, mid + 1, r);


    //归并合二为一，这里是用了双指针的技巧，将两个有序数组合成一个有序数组
    int k = 0, i = l, j = mid + 1;
    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 ++ ];

    //将结果放进原数组
    for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];
}

int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);

    merge_sort(a, 0, n - 1);

    for (int i = 0; i < n; i ++ ) printf("%d ", a[i]);

    return 0;
}

边界情况分析

归并排序因为同样也属于分治算法，最怕的就是 n分成0和n，或 n分成n和0,这会造成无限划分，所以要注意边界问题。

看一下递归的这一部分

1
merge_sort(q, l, mid), merge_sort(q, mid + 1, r);

对于这一部分，能否写成merge(q, l, mid - 1), merge_sort(q, mid, r)？
对于上述模板不可以，模板中mid = l + r >> 1，这里是下取整，所以可能会取到l，那么这个时候会出现sort(q, l ,r)，那么就会造成无线划分，死循环。

但是如果我们将mid = l + r + 1 >> 1,这里就是向上取整，不可能取到l，只可能取到r，那么对于merge(q, l, mid - 1), merge_sort(q, mid, r)就不会出现sort(q, l ,r)的情况了，但是对于原模版merge_sort(q, l, mid), merge_sort(q, mid + 1, r);则会出现sort(q, l ,r)的情况，造成无限划分，所以边界问题其实很灵活，要具体分析。归根结底就是要避免划分n和0这种情况，在这里就是避免出现sort(q, l r)。


算法分析

空间复杂度
归并的空间复杂度就是那个临时的数组和递归时压入栈的数据占用的空间：O(n) + O(logn)
所以空间复杂度为: O(n)

时间复杂度
对于分治问题的时间复杂度，我们都首先写出递推公式
T[n] = 2T[n/2] + O(n)

这个公式是怎么来的呢，它的意思是把一个规模为n的问题分成两个规模分别为n/2的子问题，时间为2T(n/2).然后分割和合并时间复杂度为O(n)。

接下来whatever你用递归树还是主方法都很容易证明T(n) = O(nlogn),我个人比较推崇主方法，确实很简单，递归树的方法可能会让你对递归程序的函数调用栈的理解更深刻一些。

因为归并排序，每次都是选取中点进行分割，所以不会造成像快速排序的最坏情况（每次划分只得到一个比上一次划分少一个记录的子序列），因此该递推公式适用于所有情况，最好，平均，最坏时间复杂度都是O(nlogn)。

稳定性
归并排序算法中，归并最后到底都是相邻元素之间的比较交换，并不会发生相同元素的相对位置发生变化，故是稳定性算法。


788. 逆序对的数量

基本思路

朴素做法，枚举每一个数，然后统计每一个数的逆序对，时间复杂度$O(n^2)$集合数据范围来看肯定是会超时的，所以需要优化
如何优化呢，这里利用归并排序的过程，统计逆序对的数量
逆序对的出现总共有三种情况

  1. 都在左边
  2. 都在右边
  3. 一左一右

注意事项：

  1. 统计第三种情况的时候，我们需要以j来划分 因为对于每一个j，i所在区间的所有逆序对情况可以确定，即[i, mid]里q[i] > q[j], [l, i - 1]里q[i] < q[j]

    因为i和j都是从头判断的，所以前面的数必然已经判断过

    但如果用i来划分，对于每个i，我们只能知道[mid + 1, j]里q[i] > q[j],可以构成逆序对，但是对于[j + 1, r]这一段区间，我们无法确定q[i] 是否大于 q[j],所以会漏掉一些情况

  2. 逆序对的数量可能超过10^9，所以我们用longlong来存

所以我们可以基于归并排序的模板，求解这道题目
时间复杂度：$O(nlogn)$
空间复杂度：$O(logn)$

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include<iostream>

using namespace std;

typedef long long LL;

const int N = 1e5 + 10;
int n;
int q[N], tmp[N];

LL merge_sort(int l, int r){
    if(l >= r) return 0;

    int mid = l + r >> 1;
    // 逆序对在左右两边
    LL res = merge_sort(l, mid) + merge_sort(mid + 1, r);

    int i = l, j = mid + 1, k = 0;
    while(i <= mid && j <= r){
        if(q[i] <= q[j]) tmp[k++] = q[i++];
        else{
            //逆序对一左一右
            res += mid - i + 1;
            tmp[k++] = q[j++];
        }
    }
    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;
}

int main(){
    cin >> n;

    for(int i = 0; i < n; i++) scanf("%d", &q[i]);

    cout << merge_sort(0, n - 1) << endl;

    return 0;
}

Reference

[1]. yxc
[2]. Bug-Free
[3]. Kir


相关题目

如果想专注于算法部分，忽略oj部分，可以尝试一下leetcode题目。
LeetCode 912. 排序数组
LeetCode 215. 数组中的第K个最大元素
剑指 Offer 51. 数组中的逆序对


算法 > AcWing
#算法 #排序
acwing算法笔记-快速排序+归并排序
https://vendestine.com/quick-sort
Author
Wenzhe Li
Posted on
March 16, 2022
Licensed under