左神课程笔记

前置基本问题:

1. 归并分治算法

大范围的答案 等不等于 左边部分 + 右边部分 + 跨越左右两边的答案

💡考虑跨左右 有序是否能提升便捷性。

  • 归并排序:

💡归并排序是一个稳定的排序。

分成左右，merge排序

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int a[N];
int help[N];


void merge(int l,int r){
    int i = l, j = ((l + r) >> 1) + 1, t1 = 0;


    while(i <= ((l + r)>> 1) && j <= r){
          help[t1++] = (a[i] <= a[j]) ? a[i++] : a[j++];}
    while(i <= ((l + r)>> 1) ){. help[t1++] = a[i++];  }
    while(j <= r){. help[t1++] = a[j++];  }


    for(i = r; i >=l; i--){. a[i] = help[--t1];  }
}
void guibin(int l, int r,int n){
     if(l >= r) return ;


     guibin(l, (l + r) >> 1, n);
     guibin(((l + r) >> 1)+1, r, n);
     merge(l, r);
}
  • 归并分治

💡

归并分治是基于归并排序，在归并排序的基础上进行分 左右 + 左右中的过渡，主要是分析左右中的过渡过程是否跟左右部分的有序性相关。

2. 随机快速排序

基本内容与快速排序保持一致，只是在选择pivot的时候是随机选择。