【算法】分治初步
目录
- 定义
- 示例
- 快速排序
- 实现
- 第k小
- 三分法
- 归并排序
- 实现
- 快速排序
定义
分治，字面上的解释是“分而治之”，就是把一个问题分成多个的相同或相似的子问题，直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。
示例
快速排序
把原数组分成左右两段，保证左 \(≤\) 右，再对左右分别排序。
实现
怎么才能让左不大于右呢？
基准值：左/右/中点/随机位置的值。 这么草率？
反正都一样。
对 \([l,r]\) 区间排序：
i = l, j = r; 确定基准值x;。- i向后走，当
a[i]>x时停下，j向前走，当a[j]>x时停下。 if(i < j) swap(a[i], a[j]);。- 当i<j时，回到第二步。
- 对 \([l, j]\) 和 \([i, r]\) 分别递归，直到
l >= r。
$\color{green}{\text{点击查看代码}}$
void quick_sort(int l, int r)
{
int i = l, j = r;
int x = a[(l+r)/2]; // 基准值（此处取中点，一般建议随机数）
while(i<=j)
{
while(a[i] < x) i++;
while(a[j] > x) j--;
// i 表示小于基准值的下标，j 表示大于基准值的下标
// 找到不满足以上的 a[i], a[j]
if(i<=j) // 如果 i 在 j 左边，a[i] 和 a[j] 交换
{
swap(a[i], a[j]);
i++,j--; // 防止越界 RE
}
}
if(l<r) // 如果数列可以再分，递归
{
quick_sort(l,j);quick_sort(i,r);
}
}
第k小
同快速排序。
但我们可以考虑一些神奇的方法。
对 \([l,r]\) 区间排序，找第 \(k\) 小：
qsort(l,r,k)
{
选基准值，做交换。
if(k <= j) return qsort(l,j,k);
else if(k >= i) return qsort(i, r, k);
else return x;
}
$\color{green}{\text{点击查看代码}}$
int quick_sort_mink(int l,int r,int k)
{
int i = l, j = r;
int x = a[(l+r)/2];
while(i<=j)
{
while(a[i] < x) i++;
while(a[j] > x) j--;
if(i<=j)
{
swap(a[i],a[j]);
i++,j--;
}
}
if(k <= j) return quick_sort_mink(l,j,k);
else if(k >= i) return quick_sort_mink(i,r,k);
else return x;
}
三分法
例题：P1883 函数
归并排序
先对左右子区间排序，然后再把两个有序子区间合并成一个完整区间。
时间复杂度：稳定的 \(O(n \log n)\)。
实现
当前区间 \([l,r]\) ：
mid=(l+r)/2;- 递归 \([l,mid]\) ;
- 递归 \([mid+1,r]\) ;
- 合并 \([l,mid],[mid+1,r]\) ;
$\color{green}{\text{点击查看代码}}$
void merge_sort(int l, int r)
{
if(l >= r) return; // 不可再分就不继续了
int mid = (l+r)/2;
merge_sort(l, mid);
merge_sort(mid+1, r);
// 递归左右区间
int i = l, j = mid+1; // 从两区间左端点开始
int cnt = l-1;
while(i <= mid && j <= r)
{
if(a[i] <= a[j]) b[++cnt] = a[i], i++;
else b[++cnt] = a[j], j++;
// 把a[i],a[j]更大的那个放进临时数组b[]
}
while(i <= mid) b[++cnt] = a[i], i++;
while(j <= r) b[++cnt] = a[j], j++;
// 把没放完的放进b[]
for(int k = l;k <= r;k++) a[k] = b[k];
// 把b[] 放回原区间
}