【精选】AcWing算法基础课（一）基础算法

您所在的位置：网站首页 › acwing算法基础课视频 › 【精选】AcWing算法基础课（一）基础算法

【精选】AcWing算法基础课（一）基础算法

2023-10-27 15:55| 来源: 网络整理| 查看: 265

文章目录 1.1 排序 1.2 二分搜索 1.3 高精度 1.4 前缀和与差分 1.5 双指针算法 1.6 位运算 1.7 离散化 1.8 区间合并

1.1 排序快速排序归并排序

快速排序（不稳定的排序）

分治思想

步骤（对左边界为l，右边界为r的一段数进行排序）：

确定分界点：q[l], q[(l + r) / 2], q[r], 随机值调整区间（重点）：通过x对区间进行划分，使得左边区间都≤x，右边区间都≥x（左右区间不一定相等）递归处理左右两个区间

调整区间的方式：

设置两个指针i，j分别指向区间的左右两个元素 i指针向右移动，直至其指向的元素≥x，停下 j指针向左移动，直至其指向的元素≤x，停下交换i，j所指向的元素（两个指针分别向中间移动一位）若i和j相遇，结束；否则跳至步骤2

一个模板：

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); }

代码解释：

第3行i和j分别先往两端偏移1的原因使每一次两个数进行交换后都需要往中间走一步，因此索性在每次执行之前就走一步，而开始需要事先向两端偏移1才能抵消该操作带来的错误影响

一个边界问题：9、10行中可以为(q, l, j)、(q, j + 1, r)，这种情况x不能取q[r]和中间值上取整（(l + r + 1) / 2），或者(q, l, i - 1)、(q, i, r)，这种情况x不能取q[l]和中间值下取整（(l + r - 1) / 2），否则都将产生死循环，如q[2] = {1, 2}，若x的取值不符要求，则会发生一直执行quick)_sort(q, 0, 1)的死循环。

若需要使快排为稳定的排序，可将元素扩展成值和下标的二元组后进行排序（但无意义）

归并排序（稳定的排序）

同样是分治思想

步骤（对左边界为l，右边界为r的一段数进行排序）：

确定分界点：mid = (l + r) / 2 递归排序左半部分和右半部分归并——合二为一

主要思想（双指针）：两个指针分别对应数组左半部分和右半部分（均已排好序），然后两个指针均向右移动，比较两个指针的值的大小，值小的依次放入用于存储排好序后的结果的数组（升序排序）

一个模板：

//首先定义一个与q数组类型、大小相同的数组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, i = l, j = mid + 1; while (i

【本文地址】

【精选】AcWing算法基础课（一）基础算法

【精选】AcWing算法基础课（一）基础算法

今日新闻

推荐新闻