算法实现

有一些算法已经被标准库实现了，但是由于这些算法太出名，很容易进行改编，因此需要掌握这些算法的具体实现

排序

归并排序

二路合并

/* 合并左子数组和右子数组 */
void merge(vector<int> &nums, int left, int mid, int right) {
    // 左子数组区间为 [left, mid], 右子数组区间为 [mid+1, right]
    // 创建一个临时数组 tmp ，用于存放合并后的结果
    vector<int> tmp(right - left + 1);
    // 初始化左子数组和右子数组的起始索引
    int i = left, j = mid + 1, k = 0; //k为临时数组索引
    // 当左右子数组都还有元素时，进行比较并将较小的元素复制到临时数组中
    while (i <= mid && j <= right) {
        if (nums[i] <= nums[j]) //这里的<=保证了排序稳定性
            tmp[k++] = nums[i++];
        else
            tmp[k++] = nums[j++];
    }
    // 将左子数组和右子数组的剩余元素复制到临时数组中
    while (i <= mid) {
        tmp[k++] = nums[i++];
    }
    while (j <= right) {
        tmp[k++] = nums[j++];
    }
    // 将临时数组 tmp 中的元素复制回原数组 nums 的对应区间
    for (k = 0; k < tmp.size(); k++) {
        nums[left + k] = tmp[k];
    }
}

归并

/* 归并排序 */
void mergeSort(vector<int> &nums, int left, int right) {
    // 终止条件
    if (left >= right)
        return; // 当子数组长度为 1 时终止递归
    // 划分阶段
    int mid = left + (right - left) / 2;    // 计算中点
    mergeSort(nums, left, mid);      // 递归左子数组
    mergeSort(nums, mid + 1, right); // 递归右子数组
    // 合并阶段
    merge(nums, left, mid, right);
}

桶排序

适用范围较广，排序前首先需要除以序列中最大的绝对值，将整个序列变成 $[0, 1)$ 范围

/* 桶排序 */
void bucketSort(vector<float> &nums) {
    // 初始化 k = n/2 个桶，预期向每个桶分配 2 个元素
    int k = nums.size() / 2;
    vector<vector<float>> buckets(k);
    // 1. 将数组元素分配到各个桶中
    for (float num : nums) {
        // 输入数据范围为 [0, 1)，使用 num * k 映射到索引范围 [0, k-1]
        int i = num * k;
        // 将 num 添加进桶 bucket_idx
        buckets[i].push_back(num);
    }
    // 2. 对各个桶执行排序
    for (vector<float> &bucket : buckets) {
        // 使用内置排序函数，也可以替换成其他排序算法
        sort(bucket.begin(), bucket.end());
    }
    // 3. 遍历桶合并结果
    int i = 0;
    for (vector<float> &bucket : buckets) {
        for (float num : bucket) {
            nums[i++] = num;
        }
    }
}

计数排序

对于非负整数序列，并且序列最大值并不特别大的，可以使用计数排序；计数排序是桶排序的特殊情况；

/* 计数排序 */
// 简单实现，无法用于排序对象
void countingSortNaive(vector<int> &nums) {
    // 1. 统计数组最大元素 m
    int m = 0;
    for (int num : nums) {
        m = max(m, num);
    }
    // 2. 统计各数字的出现次数
    // counter[num] 代表 num 的出现次数
    vector<int> counter(m + 1, 0);
    for (int num : nums) {
        counter[num]++;
    }
    // 3. 遍历 counter ，将各元素填入原数组 nums
    int i = 0;
    for (int num = 0; num < m + 1; num++) {
        for (int j = 0; j < counter[num]; j++, i++) {
            nums[i] = num;
        }
    }
}

质数筛法

埃氏筛法

vector<int> prime;
vector<bool> isPrime(N, true);
 
void Era(int n){
	isPrime[0] = isPrime[1] = false;
	for(int i=2; i<=n; i++){
		if(isPrime[i]){
			prime.push_back(i);
			if((long long)i*i > n) continue;
			for(int j= i*i; j<=n; j += i){
				//因为从 2 到 i - 1 的倍数我们之前筛过了
				//这里直接从 i 的倍数开始筛选，提高筛选效率
				isPrime[j] = false;
			}
		}
	}
}

欧拉筛

vector<int> prime;
vector<bool> notPrime(N, true);
 
void Euler(int n){
	for(int i=2; i<=n; i++){
	if(!notPrime[i])}{
		prime.push_back(i);
	}
	for(int pri_j : prime){
		if(i*pri_j>n) break;
		notPrime[i*pri_j] = true;
		if(i%pri_j == 0){
			break;
		}
	}
}

堆

对顶堆

一般用于频繁增删的数据中查找分位数，即排名第 k 的数；核心：新来的数先入堆，再平衡堆的大小

//连续输入N个数，连续输出N次中位数
int N, mid;
priority_queue<int,vector<int>,greater<int>> minHeap;
priority_queue<int,vector<int>,less<int>> maxHeap;
 
for(int i=0; i<N; i++){
	int num=0;
	cin>>num;
	
	//先入堆
	if(minHeap.empty() || num>minHeap.top())
		minHeap.push(num);
	else
		maxHeap.push(num);
		
	//调整堆的大小，这里保持minHeap中元素更多
	if(minHeap.size()>maxHeap.size()+1){
		maxHeap.push(minHeap.top());
		minHeap.pop();
	}else if(minHeap.size()<maxHeap.size()){
		minHeap.push(maxHeap.top());
		maxHeap.pop();
	}
	
	if((i+1)%2==1){//有奇数个数
		mid=minHeap.top();
	}else{
		mid=(minHeap.top()+maxHeap.top())/2.0;
	}
	
	cout<<mid<< ((i==N-1)? "\n":" ");
}

图算法

DIJ 算法

DIJ 算法是在一个图中寻找从源点到其他所有点的最短路径的算法，最终结果可以用一个 vector<int> dist 来表示；

//使用邻接矩阵来存储图,矩阵中的数值表示路径权重
vector<vector<int>> graph;
 
//方便起见我们用pair类将距离和索引打包
//第一个值为距离，第二个值为索引
//定义优先队列的比较类
class cmp{
	public:
	bool operator()(pair<int,int> &a, pair<int,int> &b){
		return a.first > b.first; //基于第一个值(距离)进行排序
	}
};
 
void dij(vector<vector<int>> &graph, int src, vector<int> &dist){
	priority_queue<pair<int,int>, vector<pair<int,int>>, cmp> pq;
	dist[src]=0;
	pq.push(make_pair(0, src));
	
	while(!pq.empty()){
		int min_index = pq.top().second;
		int min_dis = pq.top().first;
		pq.pop();
		
		if(min_dis>dist[min_index])
			continue;
		
		for(int v=0;v<V;v++){ //V是一个全局变量，表示节点个数
			//这里默认graph中-1表示没有边
			if(graph[min_index][v]!=-1 && dist[min_index]!=INT_MAX && graph[min_index][v]+dist[min_index]<dist[v]){
				//符合条件，更新参数
				dist[v]=graph[min_index][v]+dist[min_index];
				pq.push(make_pair(dist[v], v));
			}
		}
	}
}

最小生成树算法

最小生成树

Kruskal 算法

核心：就是从小到大依次选边；但是有些边不能选，因为选了就会产生回路，可以使用并查集来判断是否会产生回路

int v_num, e_num;
 
// 初始化并查集
vector<int> DJSet(v_num + 1);
void initSet(){
    for (int i = 1; i <= v_num; i++){
        DJSet[i] = i;
    }
}
 
//定义查询
int findRoot(int x){
    return DJSet[x] == x ? x : DJSet[x] = findRoot(DJSet[x]);
}
 
//定义合并
void Merge(int x, int y){
    int x_root = findRoot(x);
    int y_root = findRoot(y);
    //根结点相互连接
    if(x_root<y_root){
        DJSet[y_root] = x_root;
    }else{
        DJSet[x_root] = y_root;
    }
}
 
bool cmp(array<int, 3> a, array<int, 3> b){
    return a[0] < b[0];
}
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    cin >> v_num >> e_num;
 
    //初始化并查集
    initSet();
 
    vector<array<int, 3>> edges;
    edges.reserve(e_num); //分配内存
    for (int i = 0; i < e_num; i++){
        int u, v, w;
        cin >> u >> v >> w;
        edges.push_back({w, u, v}); //内存分配后可以这样操作
    }
 
    sort(edges.begin(), edges.end(), cmp);
 
    for (auto &[w, u, v] : edges){
    	int root_u = findRoot(u);
        int root_v = findRoot(v);
        if (root_u != root_v){
            Merge(u, v);
            cout << min(u, v) << "," << max(u, v) << "," << w << endl;
        }
    }
}

Prim 算法

每次加入距离最小的点，用堆来维护

//某个结点的邻接结点结构体
struct adjNode{
    int index;    // 连接的顶点
    int cost; // 边的权值
};
 
int v_num, e_num, src;//全局变量
 
void Prim(vector<vector<adjNode>> adj){
	//初始化关键数据结构
	vector<bool> visited(v_num);
	//将将结点和边一起存储，顺序为cost,u,v
	priority_queue<array<int, 3>, vector<array<int, 3>>, greater<>> pq;
	
	//初始化源点
	visited[src]=true;
	for(auto &adj_node:adj[src]){
		pq.push({adj_node.cost, src, adj_node.index});
	}
	
	int edgeChosen=0; //已经选中的边,最多v_num-1条
	while(edgeChose<v_num-1 && !pq.empty()){
		auto [cost, u, v]=pq.top();
		pq.pop();
		if(visited[v])
			continue;
		
		//选中这条边
		visited[v]=true;
		edgeChosen++;
		
		//输出结果
		cout<<u<<" "<<v<<" "<<cost<<endl;
		
		//刷新邻接结点
		for(auto &adj_node:adj[v]){
			if(!visited[adj_node.index]){
				pq.push({adj_node.cost, v, adj_node.index});
			}
		}
	}
}
 
int main(){
    cin >> v_num >> e_num >> src;
 
    vector<vector<adjNode>> adj(v_num + 1); //邻接结点矩阵
    for (int i = 0; i < e_num;i++){
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }
 
    Prim(adj);
}

指向原始笔记的链接

并查集

可以直接使用数组 vector 来实现，最重要的功能就是查询和合并；

int v_num; //结点个数
vector<int> set(v_num);
 
// 初始化
for(int i=0; i<v_num; i++){
	set[i]=i;
}
 
//查找
int findRoot(int x)
{ return set[x]==x ? x : set[x]=findRoot(set[x]); }
 
//合并
void Merge(int x, int y){
	int x_root = findRoot(x);
	int y_root = findRoot(y);
	//这里将编号较小的根作为新的根
	if(x_root<y_root){
		set[y_root]=x_root;
	}else{
		set[x_root]=y_root;
	}
}

🪴Morethan's Knowledge Base

探索