AcWing算法基础课学习笔记第一讲基础算法 1. 排序

小咪咪 2024-03-16 11:52 10阅读 0赞

### AcWing算法基础课学习笔记 ###

#### 文章目录 ####

*   *  AcWing算法基础课学习笔记
     *   *   *  第一讲 基础算法
             *   *  1. 排序

![在这里插入图片描述][14a48169082340d78e6c2bf93a2a29d4.png_pic_center]

##### 第一讲 基础算法 #####

> 包括排序、二分、高精度、前缀和与差分、双指针算法、位运算、离散化、区间合并等内容。

![在这里插入图片描述][e69dc7e49bdb4719bdd24d09378ed445.png_pic_center]

语法基础课以及看完了，

> 算法基础课没有课件，y 总课上主要就是讲主要思想

###### 1. 排序 ######

*  快速排序【不稳定的，当然可以变成稳定的】
    
     *  基于分治
     *  步骤：
        
         *  ① 确定分界点，q\[l\]、q\[(l + r) / 2\]、q\[r\]、随机x
         *  ② 调整区间，<=x 在左，>=x 在右【\*\*\*\*\*】
            
             *  实现：双指针i 和 j 同时往中间走
             *  其实中间会遇到很多边界问题，解决办法就是背模板
         *  ③ 递归处理左右两段
     *  时间复杂度： n l o g n nlogn nlogn
 *  归并排序【稳定的】
    
     *  分治主要思想【快排是用一个数来分，归并是用中间点分】
     *  步骤
        
         *  ① 确定分界点，`mid = (l + r) >> 1`
         *  ② 递归排序左边、右边
         *  ③ 归并，两个有序的数组合并成一个，合二为一【\*\*\*\*\*】
     *  双指针算法，比较两个数组
     *  时间复杂度： n l o g n n logn nlogn

`AcWing 785. 快速排序`

#include <iostream>
    
    using namespace std;
    
    const int N = 1e6 + 10;
    int n;
    
    int q[N];
    
    void quick_sort(int q[], int l, int r)
    {
        
        if(l >= r) return ;
        
        int x = q[l + r >> 1], i = l - 1, j = r + 1;
        
        while(i < j)
        {
            
            do i ++; while(q[i] < x); // 遇到>= x 的数停下【即< x的数都在左边】
            do j --; while(q[j] > x); // 遇到<= x 的数停下【> x的数都在右边】
            
            if(i < j) swap(q[i], q[j]); 
        }
        
        quick_sort(q, l, j);
        quick_sort(q, j + 1, r);
    }
    
    int main()
    {
        
        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;
    }

> 输入数据较多时，注意选择比较快的那种，这里别犹豫，用`scanf` 和 `printf`
> 
> > 需要注意的就是别取到边界，不然会死循环【直接背就行了】

习题：`AcWing 786. 第k个数` 【快选算法】

#include <iostream>
    
    using namespace std;
    
    const int N = 100010;
    
    int n, k;
    int q[N];
    
    int quick_sort(int l, int r, int k)
    {
        
        if(l == r) return q[l];
        
        int x = q[l], i = l - 1, j = 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]);
        }
        
        int sl = j - l + 1; // 左半边数的个数
        
        if(k <= sl) return quick_sort(l, j, k);
        
        return quick_sort(j + 1, r , k - sl);
    }
    
    int main()
    {
        
        cin >> n >> k;
        
        for(int i = 0; i < n; i ++ ) cin >> q[i];
        
        cout << quick_sort(0, n - 1, k) << endl;
        
        return 0;
    }

> 时间复杂度 O ( n ) O(n) O(n)

`AcWing 787. 归并排序`

#include <iostream>
    
    using namespace std;
    
    const int N = 1e6 + 10;
    
    int n;
    int q[N], tmp[N]; // tmp辅助数组存储结果
    
    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; // 已经合并了多少个数
        int i = l, j = mid + 1; // i、j分别为左右数组起点
        
        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]; // 结果全部拿回来，赋值回q 数组
    }
    
    int main()
    {
        
        scanf("%d", &n);
        
        for(int i = 0; i < n; i ++) scanf("%d", &q[i]);
        
        merge_sort(q, 0, n - 1);
        
        for(int i = 0; i < n; i ++) printf("%d ", q[i]);
        
        return 0;
    }

`AcWing 788. 逆序对的数量`

#include <iostream>
    
    using namespace std;
    
    typedef long long LL;
    
    const int N = 1e6 + 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 k = 0; // 已经归并的数的个数
        int i = l, j = mid + 1;
        
        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 ++];
        
        // 重新赋值q
        for (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 ++) cin >> q[i];
        
        cout << merge_sort(0, n - 1) << endl;
        
        return 0;
    }

> 分治【归并排序的应用】
> 
> 关键是逆序对的两个数在左右两边的情况，还是双指针，在归并的时候，可以利用两个数组中的大小关系
> 
> 而且要注意`int` 爆

![在这里插入图片描述][545d2a00ffeb4f009d72d14f79e64f76.png_pic_center]

OK。

[14a48169082340d78e6c2bf93a2a29d4.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/99d5136c670440d4b830fad911979de3.png
[e69dc7e49bdb4719bdd24d09378ed445.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/ac053fadfe244b3db647af50d094109e.png
[545d2a00ffeb4f009d72d14f79e64f76.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/7b79797bd55047d7b0b91505a3d14a73.png