目录

Acwing算法基础课算法笔记

本讲主要内容
快速排序,归并排序,高精度,前缀和,差分,双指针,位运算,离散化,区间合并。

快速排序

思想

双指针来遍历调整区间,并不断递归处理,最后使得所有子区间有序,具体步骤如下(不要忘记递归结束条件):

  1. 取分界点并初始化指针
  2. 调整区间。若有指针遇到了不符合条件的数,则停下来,等两个指针都遇到了不符合条件的数,且i在j左边,交换他们所指向的数
  3. 划分子区间递归处理
  4. 处理到子区间只有一个数字时结束递归
    可以任意举一组数据,画图帮助理解(类似递归树结构的图)。

注意点

平均时间复杂度为$O(nlogn)$,最坏时间复杂度会退化为$O(n^2)$。
如果递归条件写为(即j的对称改一下的形式,两种都可以)
quick_sort(q, l, i - 1); quick_sort(q, i, r);
则x不能取q[l]
同理,若写为
quick_sort(q, l, j);quick_sort(q, j + 1, r);
则x不能取q[r]
否则会不断划分成(0,n)(n,0),一直递归造成死循环。
另外在取分界点时最好取中点或者随机取,可以避免部分因为取左右边界点,使得快排复杂度退化为$O(n^2)$而超时的情况。

快速选择算法

思想

是基于快排改进的。
在划分子区间递归处理子区间时,只递归一边,看k大的数属于左区间还是右区间即可,思想和二分有一点类似。根据区间个数与k的关系来递归处理。
对于递归结束条件的解释:第k大的数所在的区间只有一个数,那么这个数就是整个区间第k大的数。
递归处理时:
如果在左半区间,由于子区间已经有序,那么整个区间第k大的数就在这个区间的前k个元素中。
反之,在右半区间的位次就是整个区间第k大的数的位置减去左半区间的元素个数。
同样的,可以手工模拟帮助理解。

注意点

时间复杂度为$O(n)$。

归并排序

思想

先递归处理划分区间,使得子区间有序,合并后再次使得合并后的区间有序,这样合并完成后,整个区间就有序了。步骤如下:

  1. 划分子区间。注意是均分的。
  2. 递归处理。处理到子区间只有一个数字时结束递归,此时划分区间结束。开始递归处理子区间。
  3. 合并子区间到临时数组tmp中。这里用临时数组是为了不破坏子区间对于整个区间的相对位置,也就是先让子区间中的数相对于子区间有序,在合并子区间的过程中,区间合并后不断扩大到整个区间,最后每个子区间中的数就相对于整个区间有序。
  4. 清理子区间中还没有放到临时数组tmp的数字。合并子区间到临时数组中也是用的双指针思想,若子区间中还有剩余的数,直接接到临时数组tmp后面就行,因为是递归处理的,此时它们已经是有序的了。
  5. 将临时数组中的数字存回原数组。合并结束前,它们在原数组中只是相对于子区间有序,合并结束后就相对于整个原数组有序了。

注意点

归并排序的平均时间复杂度和最坏时间复杂度都是$O(nlogn)$。
它的模板有几种写法,记住最容易理解和记忆的即可。