AcWing算法基础课学习笔记 第一讲 基础算法 1. 排序 小咪咪 2024-03-16 11:52 52阅读 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
相关 AcWing算法基础课学习笔记 第一讲 基础算法 2. 二分 AcWing算法基础课学习笔记 文章目录 AcWing算法基础课学习笔记 第一讲 基础算法 叁歲伎倆/ 2024年03月16日 11:53/ 0 赞/ 58 阅读
相关 AcWing算法基础课学习笔记 第一讲 基础算法 1. 排序 AcWing算法基础课学习笔记 文章目录 AcWing算法基础课学习笔记 第一讲 基础算法 小咪咪/ 2024年03月16日 11:52/ 0 赞/ 53 阅读
相关 acwing算法基础课学习笔记(第一章:基础算法) 第一章:基础算法 前言 一、快速排序 1. 快速排序算法模板 2. 快速排序模板题(1):快速排序 3.快速排序算法模 小鱼儿/ 2023年09月28日 18:18/ 0 赞/ 32 阅读
相关 Acwing - 算法基础课 - 笔记(五) 文章目录 数据结构(二) Trie树 练习题:\[Acwing - 835: Trie字符串统计\](http 约定不等于承诺〃/ 2022年10月06日 04:59/ 0 赞/ 162 阅读
还没有评论,来说两句吧...