<– 👍 ♥

目录

快排

----------------------------------------------分割线-------------------------------------------------

快排:O(nlogn)

void quick_sort(int l, int r){
    if(l >= r)return;
    int left = l - 1, right = r + 1, x = a[l + r >> 1];
    //把a[l...r]每一个元素分到不同部分
    for(int k = l; k != right; ++ k){//right及往后的都已经处理过了,这里!=right是为了不重复处理
        if(a[k] < x){
            ++ left;//“申请”一个空间
            swap(a[left], a[k]);//“加入”元素
            //由于a[l...k-1]的元素已经被处理过了，所以即使交换后也不需要对交换的值再次处理，因为它一定=x
        }else if(a[k] > x){
            -- right;//“申请”一个空间
            swap(a[k], a[right]);//“加入”元素
            -- k;//for中k自动+1,这里--是为了不漏掉没有处理的元素
        }
    }
    quick_sort(l, left);
    quick_sort(right, r);
}

思路

把a[l…r]分为3部分:a[l...left] < 基准值, a[right...r] > 基准值和a[left+1...right-1] = 基准值(这一步自动完成)。分完后对a[l...left]和a[right...r]继续递归。
----------------------------------------------分割线-------------------------------------------------

并查集find函数(非递归)

int find(int x) {
    vector<int> vct = {x};
    while(vct.back() != f[vct.back()]) vct.push_back(f[vct.back()]);//往上找
    int t = vct.back();vct.pop_back();//找到了
    while(vct.size()){//更新
        f[vct.back()] = t;
        vct.pop_back();
    }
    return f[x];//返回
}