C++/C算法n0t3 # «算法» # qsort快排(c语言) # 1.qsort函数原型
1void qsort(void *base, size_t nmemb, size_t size, 2 int (*compar)(const void *, const void *)); 2.具体写法 （1）先写比较函数 （返回的是整形）
1// 升序排序（从小到大） 2int cmp_asc(const void *a, const void *b) { 3 return (*(int*)a - *(int*)b); 4} 5// 降序排序 （从大到小） 6int cmp_desc(const void *a, const void *b) { 7 return (*(int*)b - *(int*)a); 8} 解释：因为排序的类型可能是int,double等各种，所以用const voida表示可以指向任何类型的指针，然后在return中先将a转化成对应题目类型的指针例如（int） ，再在前面加* 表示指针所指的具体值 （2）再在主函数中调用
1qsort(a,n,sizeof(int),cmp); a表示要排序的数组的首地址 n表示数组长度 sizeof（int）表示这个数组类型的数据长度 cmp是提前写好的比较函数的名称 3.原理 比较函数cmp中，（有点难理解但很重要！！） 若返回负值—>将参数a排在参数b前面 若返回0—>参数a，参数b顺序不变 若返回正值—>将参数a排在参数b后面 依此可以写各种其他不同排序：（待开发）
例题 # 排队接水 # 知识点：
下标索引的理解,选择排序，原始编号移动，前缀和
解法：
1#include <bits/stdc++.h> 2using namespace std; 3int main(){ 4 int n; 5 cin>>n; 6 double time[n]; 7 int original_index[n];//设立原始编号，很重要 8 for(int i = 0;i<n;i++){ 9 cin>>time[i]; 10 original_index[i] = i+1; 11 } 12 for(int i = 0;i<n;i++){ 13 int minindex = i; 14 for(int j = i+1;j<n;j++){ 15 if(time[j]<time[minindex]){//利用选择排序从小到大选出索引，完成第一行输出 16 minindex = j; 17 } 18 } 19 cout<<original_index[minindex]<<" "; 20 swap(time[i],time[minindex]);//防止重复，还是需要交换元素 21 swap(original_index[i],original_index[minindex]);//原始编号也要跟着它主人一起移动交换 22 } 23 cout<<endl; 24 double sum = 0; 25 26 double pre[n];//计算每个人除了自己接水，需要额外等待的时间 27 pre[0] = 0;//第一个人额外等待时间为0 28 for(int i = 1;i<n;i++){//从第二个人开始 29 pre[i] = time[i-1]+pre[i-1];//等于他前一个人接水时间加上前一个人额外等待时间 30 } 31 32 for(int i = 0;i<n;i++){//计算等待总时间 33 sum = sum+pre[i];//修改为正确的等待时间 34 } 35 double average = sum/n; 36 cout<<fixed<<setprecision(3)<<average; 37 return 0; 38} 重点在于原始编号按题目要求改变后，能够正确输出
图论基础 # 图的存储 # 邻接表存图 # 对于每一个节点，记录这个几点连接的所有其他节点和对应权值
1#include <bits/stdc++.h> 2using namespace std; 3const int N = 100010; 4vector<pair<ll,int> graph[N];//图,{权值,对应的节点} 5int n,m; 6int main(){ 7 cin>>n>>m; 8 for(int i = 0;i<m;i++){ 9 int u,v,w; 10 cin>>u>>v>>w; 11 graph[u].push_back({w,v}); 12 graph[v].push_back({w,u}); 13 } 14} 邻接矩阵存图 # 用一个二维数组记录每两个点之间的距离