【acwing算法基础课笔记】01-基础算法-分治
发布时间
阅读量：
阅读量
快速排序 - 分治
1、分界点 `q[1]、q[len/2]、q[r]随机
2、调整区间，大于x一边小于x一边
3、递归调整左右两段
边界问题
必须先j++后i++
一、中间没有需要排序的元素，ij相邻
j先走向左停在i上，i是偏小的一方，与l互换正好一个在中间一个在小的一边
二、中间是一个偏大的元素，ij在这元素两边
j先走会跳过大的，停在偏小i的上，同一
三，中间是一个偏小的元素，j停在中间元素上，i再向右走
大的跳过到小的，同一
https://leetcode.cn/leetbook/read/illustration-of-algorithm/p57uhr/
int partition(vector<int>& nums, int l, int r) {
// 以 nums[l] 作为基准数
int i = l, j = r;
while (i < j) {
while (i < j && nums[j] >= nums[l]) j--;
while (i < j && nums[i] <= nums[l]) i++;
swap(nums[i], nums[j]);
}
swap(nums[i], nums[l]);
return i;
}
void quickSort(vector<int>& nums, int l, int r) {
// 子数组长度为 1 时终止递归
if (l >= r) return;
// 哨兵划分操作
int i = partition(nums, l, r);
// 递归左（右）子数组执行哨兵划分
quickSort(nums, l, i - 1);
quickSort(nums, i + 1, r);
}
// 调用
vector<int> nums = { 4, 1, 3, 2, 5, 1 };
quickSort(nums, 0, nums.size() - 1);
c
 public void SortArr(int[] arr, int left, int right) {
// 有请快速排序选手登场
if (left >= right) { return; } // 数组只有一个元素或者没有，那么不需继续递归
int indexL = left;
int indexR = right;
int sentry = arr[left];
int swap;
while (indexL < indexR) {
while (indexL < indexR && arr[indexR] >= sentry) { indexR--; }
while (indexL < indexR && arr[indexL] <= sentry) { indexL++; }
swap = arr[indexL]; arr[indexL] = arr[indexR]; arr[indexR] = swap;
// 两个指针靠近，顺便保证自己身后没有比哨兵大/小的元素
}
// 把哨兵搬到两个指针的位置，这样保证了哨兵两边元素都比它大/小
swap = arr[left]; arr[left] = arr[indexL]; arr[indexL] = swap;
// 对数组进行哨兵划分
SortArr(arr, left, indexL - 1);
SortArr(arr, indexL + 1, right);
// 然后继续对子数组做哨兵划分（哨兵两边的数组，不包括它本身），分治
}
/*
两个问题：
1.为什么比较指针和哨兵要用>=或<=，而不用>或<？
2.为什么左指针右移和右指针左移顺序不能互换？
解：1.如果不忽略相等情况，那么就可能L和R数值都等于哨兵，恭喜你，交换后再交换，死循环，
实际上，与哨兵相等的元素无论在子数组的哪边都不影响结果，所以直接忽略没啥问题。
2.快速排序必须保证最后哨兵左边的元素小于等于之，在两个指针靠近的时候，左指针的左边都可以满足这个条件；
但是，当两个指针相撞的时候就不好说了；如果我们在循环中让左指针先走，有如下情况会发生：
左指针撞在一个大于哨兵的数上，结果右指针撞上了左指针，这个大数被交换到了哨兵左边，导致排序错误。
如果我们让右指针先走，就可以避免这个问题：左指针要么撞上更大的数，做交换，要么撞上右指针，右指针会停下来肯定是因为这个数比哨兵小，所以被交换到哨兵左边的数仍然小于哨兵，条件满足。
*/
c
归并排序 - 分治
1、确定分界点 mid = (1+r)/2
2、递归排序 left、right
3、归并 - 合二为一
#include <iostream>
using namespace std;
const int N = 36;
int q[N],tmp[N];
// 归并排序 类似后序遍历
void merge_sort(int q[],int left,int right){
if(left>=right) return;
int mid = (left + right) >> 1; // 确定分界点
merge_sort(q,left,mid); // 左子数组排序
merge_sort(q,mid+1,right); // 右子数组排序
// 合并两子数组到tmp，k是tmp的指针，i,j指向左/右子数组头部
int k=0,i = left, j = mid +1 ;
while(i<=mid && j <=right){
if(q[i]<=q[j])tmp[k++]=q[i++];
else tmp[k++]=q[j++];
}
// 复制没到头的偏大一坨
while(i <= mid)tmp[k++]=q[i++];
while(j <= right)tmp[k++]=q[j++];
// 把合并后的tmp 复制到 原数组
for(i=left,j=0;i<right;++i,++j)
q[i]=tmp[j];
}
int main(){
for(int i=N-1;i>=0;--i){
q[i]=i;
}
merge_sort(q,0,N-1);
for(int i=0;i<N;++i){
cout << q[i] << endl;
}
}
C
空间O(n)
时间O(logN) 平均
整数二分 - 不常考
为什么+1，为真可能不会改变检查范围，为假一定会消减一部分，所以尽量让mid往假的那边靠 ，防止死循环
也就是说，+1靠近假，就+，不+靠近假，就不加
#include <iostream>
using namespace std;
const int N = 100010;
int n,m;
int q[N];
int main()
{
//n数组长度 m询问长度
scanf("%d%d",&n,&m);
//读入整个数组
for(int i = 0;i < n;i++ ) scanf("%d",&q[i]);
//一共有m个询问,对于每一个询问分别来做
while(m-- )
{
//x是要查找的值
int x;
scanf("%d",&x);
//定义左右边界
int l = 0,r = n - 1;
//二分找左边的边界点:找起始坐标,找第一个大于等于x的数
while(l < r)
{
//中间值:是否需要补上加 1 可以后面再考虑
int mid = l + r >> 1;
//r = mid 使用的是第二个模板 不需要补上加 1
if(q[mid] >= x) r = mid;
else l = mid + 1;
}
//当找到满足大于等于x的第一个数不等于x时,说明数组中不存在x
if(q[l] != x) cout << "-1 -1" << endl;
else
{
//输出 l 和 r 是一样的 循环结束后 l 和 r 是相等的
cout << l << ' ';
int l = 0,r = n - 1;
//二分找右边的边界点:找终止坐标,找最后一个小于等于x的数
while(l < r)
{
int mid = l + r + 1 >> 1;
//l = mid 使用第一个模板需要补上加 1
if(q[mid] <= x) l = mid;
else r = mid - 1;
}
cout << l << endl;
}
}
return 0;
}
C
浮点数二分
/*
浮点数二分 - 求一个数的平方根
*/
#include <iostream>
using namespace std;
int main(){
double x;
cin >> x;
double l =0,r=x;
while(r-l > 1e-6){
double mid = (l+r)/2;
if(mid*mid>x)r=mid;
else l=mid;
}
cout << l << endl;
return 0;
}
c
全部评论 (0)
还没有任何评论哟~