1 桶排序
2 冒泡排序
3 快速排序
4 队列,栈,链表
5 弗洛伊德算法 -最短路径:求两个城市之间的最短路径
6 迪杰斯特拉算法 -单源最短路径:指定一个点到其余各个顶点的最短路径
7 贝尔曼福特算法(优化) -单源最短路径:解决了负权边的问题
8 堆
9 堆排序
10 并查集
1 桶排序
//根据最大值设立桶数,每出现一个数,就在对应编号的桶中放旗子做标记,最后根据旗子数打印桶序数
//时间复杂度为O(m+n),但是浪费空间
void tong(){
printf("开始桶排序\n");
int tong[1001],i,j,t,n;
for (i = 0; i <= 1000; i++)
{
tong[i] = 0;
}
//输入一个数n,表示接下来有n个数
printf("输入数据个数\n");
scanf("%d",&n);
//循环读入n个数,并进行桶排序
printf("输入数据\n");
for (i = 1; i <= n; i++)
{
scanf("%d",&t);
//计数,对编号为t的桶插一个旗子
tong[t]++;
}
printf("桶排序完成\n");
//依次判断带编号的桶
for (i = 1000; i >= 0; i--)
{
//出现几次就将桶编号打印几次
for (j = 1; j <= tong[i]; j++)
{
printf("%d\n",i);
}
}
}
2 冒泡排序
//每次都比较两个相邻的元素,如果它们的顺序错误就把它们交换过来,顺序正确位置不变,继续比较
//时间复杂度是O(n²)
void maoPao(){
printf("开始冒泡排序\n");
int a[100],i,j,n;
printf("输入数据个数\n");
scanf("%d",&n);
printf("输入数据\n");
//循环读入数据
for (i = 1; i <= n; i++)
{
scanf("%d",&a[i]);
}
//开始排序
for (i = 1; i <= n-1; i++)
{
for (j = 1; j <= n-i; j++)
{
if (a[j] < a[j+1])
{
int temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;
}
}
}
printf("冒泡排序完成\n");
//输出
for (i = 1; i <= n; i++)
{
printf("%d\n",a[i]);
}
}
3 快速排序
//也是交换排序,每次交换是跳跃式的.
//每次排序的时候设置一个基准点(通常是第一个数),然后从两头开始比较交换,将小于等于基准点的数全部放在基准点的左边,将大于等于基准点的数全部放在基准点的右边
//平均时间复杂度O(nlogn)
//快速排序
int a[101];
//a[0,3,5,1,4,2]
//left 1 right 5
void realKuaiSu(int left,int right){
int i,j,t,temp;
if (left > right)
{
return;
}
//temp为基准数
temp = a[left];//temp=3
i = left; //i=1
j = right; //j=5
//i不等于j,就一直循环
while (i != j)
{
//从右往左找,当条件成立时,执行j--,再判断表达式,直到跳出
//2>=3 j=5 跳出
//5>=3 j=4
//4>=3 j=3
//1>=3 j=3 跳出
while (a[j] >= temp && i < j)
{
j--;
}
//j=5
//j=3
//从左往右找
//3<=3 i=2
//5<=3 i=2 跳出
//2<=3 i=3
//1<=3 i=j 跳出
while (a[i] <= temp && i < j)
{
i++;
}
//i=2
//i=3
//当两个哨兵没有相遇,交换两个数在数组中的位置
if (i < j)
{
t = a[i];
a[i] = a[j];
a[j] = t;
}
}
//a[0,3,2,1,4,5] 2!=5 循环 此时j=5 i=2 temp=3
//i=3 j=3 跳出 此时a[0,3,2,1,4,5] temp=3
//将基准数归位
a[left] = a[i]; //a[1]=1
a[i] = temp; //a[3]=3
//a[0,1,2,3,4,5]
//然后一直处理左半边的
realKuaiSu(left, i-1); //1,2
//处理右边的
realKuaiSu(i+1, right); //4,5
}
//调用快速排序
void kuaiSu(){
printf("开始快速排序\n");
int i,n;
printf("输入数据个数\n");
scanf("%d",&n);
printf("输入数据\n");
//循环读入数据
for (i = 1; i <= n; i++)
{
scanf("%d",&a[i]);
}
realKuaiSu(1, n);
printf("快速排序完成\n");
//输出
for (i = 1; i <= n; i++)
{
printf("%d\n",a[i]);
}
}
4 队列,栈,链表
//队列
//一种特殊的线性结构,只允许在队列首部进行删除操作(出列),在队列尾部进行插入操作(入列),先进先出(FIFO)
struct queue {
int data[100];//数据
int head; //队首
int tail; //队尾
};
//栈
//只能在一端进行插入和删除操作,后进后出
struct stack {
int data[10];
int top;
};
//链表
//在 C 语言中*号有三个用途，分别是:
//1. 乘号，用做乘法运算，例如 5*6。
//2. 申明一个指针，在定义指针变量时使用，例如 int *p;。
//3. 间接运算符，取得指针所指向的内存中的值，例如 printf("%d",*p);。
//->叫做结构体指针运算符，用来访问结构体内部成员的
struct node {
int data;
struct node *next;
};
void lian(){
struct node *p;
//动态申请一个空间，用来存放一个结点，并用临时指针p指向这个结点
p = (struct node *)malloc(sizeof(struct node));
}
//模拟链表
//两个数组,第一个数组存储数据,第二个数组存放每个元素右边的元素在第一个数组中位置的
//模拟链表
//两个数组,第一个数组存储数据,第二个数组存放每个元素右边的元素在第一个数组中位置的
//枚举
//又叫穷举算法,有序地尝试每一种可能
//奥数题
//炸弹人
//火柴棍等式 m根(m<=24)火柴棍,可以拼出多少个不同形状如A+B=C的等式
//枚举A,B,C,范围都是0~11111(20根火柴棍),A+B+C=m-4
//数的全排列 输入一个指定点的数n,输出1~n的全排列
//深度优先搜索
//关键在于当下该如何做
void DFS(int step){
int i,n = 0;
//判断边界
//尝试每一种可能
for (i = 1; i <= n; i++)
{
//继续下一步
DFS(step +1);
}
}
//图的遍历:以一个未被访问过的顶点作为起始顶点,沿当前顶点的边走到未访问过的顶点,当没有未访问过的顶点时,回到上一个顶点,继续访问别的顶点...一条路走到黑,然后回头
//城市地图
//广度优先搜索
//图的遍历:以一个未被访问过的顶点作为起始顶点,访问其所有相邻的顶点,然后对每个相邻的顶点再访问相邻的顶点...
//最小转机
//适用于所有边的权值相同的情况
5 弗洛伊德算法
//最短路径 有些城市之间有公路,有些城市之间没有,求两个城市之间的最短路径
//时间复杂度为O(n³),不能解决带有负权环,负权回路的图
//用二维数组存储所有点之间关系,刚开始只允许经过1顶点进行中转,慢慢增加允许中转的点数量
void Floyd(){
int n = 100,e[10][10];
for (int k=1; k<=n; k++){
for (int i=1; i<=n; i++){
for (int j=1; j<=n; j++) {
if (e[i][j] > e[i][k]+e[k][j]) {
e[i][j] = e[i][k]+e[k][j];
}
}
}
}
}
6 迪杰斯特拉算法
//单源最短路径:指定一个点到其余各个顶点的最短路径
//时间复杂度为O(n²)
//用一个二维数组存储所有点之间关系,用一个一维数组存储一个点到其他点的初始路程,称为估计值,找到最小的,称为确定值
//每次找到离源点最近的一个顶点,通过比较各路径与估计值大小,更新估计值(松弛),直到都成为确定值,即最短路线
void Dijkstra(){
//n为顶点数,e为关系数组,book为已知最短路径顶点,dis为初始路程
int n = 100,e[10][10],book[10],dis[10],u=0,v=0;
for (int i=1; i<=n-1; i++)
{
//找到离1号顶点最近的顶点
int min = 9999999;
for (int j=1; j<=n; j++)
{
if (book[j]==0 && dis[j]<min)
{
min = dis[j];
u = j;
}
}
book[u] = 1;
for (v=1; v<=n; v++)
{
if (e[u][v] < 9999999)
{
if (dis[v] > dis[u]+e[u][v])
{
dis[v] = dis[u]+e[u][v];
}
}
}
}
}
//优化
//时间复杂度为O(m+n)logn
//用邻接表存储图的时间复杂度是O(m)
//但不能有负权边
7 贝尔曼福特算法
//贝尔曼福特算法
//时间复杂度为O(mn)
//解决了负权边的问题
void BellmanFord(){
//n为顶点个数,m为边数,uvw记录边的信息
int n=10,m=10,dis[10],v[10],u[10],w[10];
for (int k=1; k<=n-1; k++)//进行n-1轮松弛
{
for (int i=1; i<=m; i++)//枚举每一条边
{
if (dis[v[i]] > dis[u[i]] + w[i])//尝试松弛
{
dis[v[i]] = dis[u[i]] + w[i];
}
}
}
}
//贝尔曼福特算法优化
//1.可以用一个一维数组备份数组dis,如果在新一轮的松弛中数量dis没有发生变化,则可以提前跳出循环
void BellmanFord1(){
//n为顶点个数,m为边数,uvw记录边的信息
int n=10,m=10,dis[10],bak[10],v[10],u[10],w[10],check,flag;
//进行n-1轮松弛
for (int k=1; k<=n-1; k++)
{
//将dis数组备份至bak数组中
for (int i=1; i<=n; i++)
{
bak[i] = dis[i];
}
//枚举每一条边
for (int i=1; i<=m; i++)
{
//尝试松弛
if (dis[v[i]] > dis[u[i]] + w[i])
{
dis[v[i]] = dis[u[i]] + w[i];
}
}
//松弛完毕后检测dis数组是否有更新
check=0;
for (int i=1; i<=n; i++)
{
if (bak[i] != dis[i])
{
check = 1;
break;
}
}
//如果dis数组没有更新,提前退出循环
if (check==0)
{
break;
}
}
//检测负权回路
flag = 0;
for (int i=1; i<=m; i++)
{
if (dis[v[i]] > dis[u[i]] + w[i])
{
flag = 1;
}
}
if (flag==1)
{
//此图含有负权回路
}
}
//贝尔曼福特算法优化
//2.每次仅对最短路程发生变化了的顶点的相邻边执行松弛操作
//用一个队列que维护这些最短路程发生变化了的点
void BellmanFord2(){
//n顶点个数,m边数,dis最短路径数组,que队列,head队列头,tail队列尾
int n,m,i,j,k;
//u,v,w大小一般要比m的最大值大1 边的数组
int u[8],v[8],w[8];
//first要比n最大值大1,next比m的最大值大1 建立邻接表用
int first[6],next[8];
//book数组记录已在队列中的顶点
int dis[6] = {0},book[6] = {0};
int que[101] = {0},head = 1,tail = 1;
//假设图为5点,7边结构
m=5,n=7;
//把边建立邻接表
for (i =1; i<=m; i++)
{
scanf("%d,%d,%d",&u[i],&v[i],&w[i]);
next[i] = first[u[i]];
first[u[i]] = i;
}
//开始算法
//顶点入列
que[tail] = 1;
tail++;
//1号已经入列
book[1] = 1;
//队列不为空循环
while (head < tail)
{
//当前需要处理的队列首顶点
k = first[que[head]];
//扫描当前顶点所有的边
while (k!=-1)
{
///尝试松弛
if (dis[v[k]] > dis[u[k]] + w[k])
{
//松弛
dis[v[k]] = dis[u[k]] + w[k];
//优化的部分,book数组判断顶点v[k]是否在队列中,节省了时间
//0表示不在
if (book[v[k]]==0)
{
//入队操作
que[tail] = v[k];
tail++;
//标记已经入队
book[v[k]] = i;
}
}
k = next[k];
}
//出队
book[que[head]] = 0;
head++;
}
//输出dis即可,这个优化在不用遍历判断,队列为空时算法结束,book数组判断是否在队列中
}
三种算法的总结
8 堆
//满二叉树
//每个结点都有两个儿子
//完全二叉树
//一棵二叉树除了最右边位置上有一个或者几个叶结点缺少外,其他是丰满的,为完全二叉树
//堆
//堆是一种特殊的完全二叉树
//所有父结点比子结点大的为最大堆,所有父结点比子结点小的为最小堆
//创建堆:把n个元素先从左到右从1到n编码,转换成一棵完全二叉树,然后从最后一个非叶结点到根结点,逐个挪动结点,直到成为堆
//最小堆应用
//删除一个数组中最小的数,并增加一个新的数,再次求这个数组中最小的一个数
//相比遍历而言,时间复杂度大大降低,为O(logn)
//插入一个新的元素同理,插在末尾,然后上移,时间复杂度也为O(logn)
void downSmall(){
//i代表顶点,h数组与n数组长度
int i=1,h[10],n=10;
//flag标记是否需要继续向下调整
int t,flag=0;
//当i结点有儿子并且需要继续调整的时候,执行循环
while (i*2<=n && flag==0)
{
//首先判断它和左儿子的关系,并用t记录值较小的结点编号
if (h[i] > h[i*2])
{
t = i*2;
}
else
{
t = i;
}
//如果有右儿子,对右儿子进行操作
if (i*2+1 <= n)
{
//如果右儿子值更小,更新小的结点编号
if (h[t] > h[i*2+1])
{
t = i*2+1;
}
}
//如果发现最小的结点编号不是自己,说明子结点中有比父结点更小的
if (t!=i)
{
int temp = h[t];
h[t] = h[i];
h[i] = temp;
//更新i为刚才与它交换的儿子结点的编号,便于向下调整
i = t;
}
//否则说明当前的父结点已经比两个子结点都要小,不需要再进行调整
else
{
flag = 1;
}
}
}
//删除最大的元素
int deletemax(){
//h一个堆,n长度
int t,h[10],n=10;
//将堆最后一个点赋值到堆顶
t = h[1];
h[1] = h[n];
//堆的元素减少1
n--;
//从顶点向下调整排序
downSmall();
return t;
}
9 堆排序
//先建立最大堆
void downBig(){
//i代表顶点,h数组与n数组长度
int i=1,h[10],n=10;
//flag标记是否需要继续向下调整
int t,flag=0;
//当i结点有儿子并且需要继续调整的时候,执行循环
while (i*2<=n && flag==0)
{
//首先判断它和左儿子的关系,并用t记录值较大的结点编号 //此处不同
if (h[i] < h[i*2])
{
t = i*2;
}
else
{
t = i;
}
//如果有右儿子,对右儿子进行操作
if (i*2+1 <= n)
{
//如果右儿子值更大,更新小的结点编号 此处不同
if (h[t] < h[i*2+1])
{
t = i*2+1;
}
}
//如果发现最大的结点编号不是自己,说明子结点中有比父结点更大的
if (t!=i)
{
int temp = h[t];
h[t] = h[i];
h[i] = temp;
//更新i为刚才与它交换的儿子结点的编号,便于向下调整
i = t;
}
//否则说明当前的父结点已经比两个子结点都要大,不需要再进行调整
else
{
flag = 1;
}
}
}
//堆排序
//每次都把堆顶最大值换到末尾,然后排除掉再排序,保持堆顶是最大值
//时间复杂度为O(nlogn)
void duiPaiXu(){
int h[10],n=10;
while (n > 1)
{
int temp = h[1];
h[1] = h[n];
h[n] = temp;
n--;
downBig();
}
}
//像这样支持插入元素和寻找最值的数据结构称为优先队列,堆就是一种优先队列
//普通队列寻找最值需要穷举,而已排序好的数组插入元素需要移动很多
//堆还可以用来求一个数列中第k大的数,要建立一个大小为k的最小堆,从k+1个数开始与堆顶比较,如果比堆顶的数要大,则舍弃当前堆顶将这个数作为堆顶,然后重新排序
10 并查集
并查集通过一个一维数组来实现,本质是维护一个森林,逐渐将树合并成一棵大树,遵循靠左原则和擒贼先擒王原则
//擒贼先擒王原则 递归函数,不停地找根树
int get(int v){
int f[10]={1,2,3,4,5,6,7,8,9,10};
if (f[v] == v)
{
return v;
}
else
{
//路径压缩 每次在函数返回的时候,把路上遇到的树的根改为最后找到的根树,可以提高其他树找到根树的速度
f[v] = get(f[v]);
return f[v];
}
}
//合并两子集合的函数
void merge(int v,int u){
int f[10]={1,2,3,4,5,6,7,8,9,10};
int t1,t2;
t1 = get(v);
t2 = get(u);
//判断两个结点是否在同一个集合中,即是否为同一个祖先
if (t1 != t2)
{
//靠左原则,左边变成右边的根数,把右边集合作为左边集合的子集合
f[t2] = t1;
}
}
void bingChaJi(){
int i,x,y,m,n,sum=0;
int f[10]={1,2,3,4,5,6,7,8,9,10};
scanf("%d %d",&n,&m);
for (i=1; i<=m; i++)
{
//合并树
scanf("%d %d",&x,&y);
merge(x,y);
}
//最后看有几个树
for (i=1; i<=n; i++)
{
if (f[i]==i)
{
sum++;
}
}
}
