算法小记

• 简单算法日记

简单算法日记

topic：最近突然对算法有了一定的兴趣，专门记录一下。

快速排序

#include<iostream>
#include<windows.h>
#include<time.h>
using namespace std;
void quickSort(int a[],int l,int r)
{
    if(l<r)
    {
        int i=l,j=r,x=a[l];
        while(i<j)
        {
            while(i<j&&a[j]>=x)
                j--;
            if(i<j)
                a[i++]=a[j];
            while(i<j&&a[i]<x)
                i++;
            if(i<j)
                a[j--]=a[i];
        }
        a[i]=x;
        quickSort(a,l,i-1);
        quickSort(a,i+1,r);
    }
}
int main()
{
    srand(time(NULL));
    int array[10];
    for(int i=0;i<10;i++)
    {
        array[i]=rand()%20;
    }
    quickSort(array,0,9);
    for(int i=0;i<10;i++)
    {
        cout<<array[i]<<" ";
    }
    cout<<endl;
    return 0;
}

简单选择排序

#include<iostream>
#include<windows.h>
#include<time.h>
using namespace std;
void SinpleChosenSort(int a[],int len)
{
    for(int i=0;i<len;i++)
    {
        int smallest=a[i];
        int smallpos=i;
        for(int j=i;j<len;j++)
        {
            if(a[j]<smallest)
            {
                smallest=a[j];
                smallpos=j;
            }
        }
        a[smallpos]=a[i];
        a[i]=smallest;
    }
}
int main()
{
    srand(time(NULL));
    int array[10];
    for(int i=0;i<10;i++)
    {
        array[i]=rand()%20;
    }
    SinpleChosenSort(array,10);
    for(int i=0;i<10;i++)
    {
        cout<<array[i]<<" ";
    }
    cout<<endl;
    return 0;
}

floyd

#include<iostream>
#include<windows.h>
#define MAXN 10
#define INF 1000
using namespace std;
typedef struct Graph_Struct
{
    int vexnum;
    int edgenum;
    int matrix[MAXN][MAXN];
}Graph;
int pMatrix[MAXN][MAXN];
int dMatrix[MAXN][MAXN];
void floyd(Graph G,int P[MAXN][MAXN],int D[MAXN][MAXN])
{
    for(int i=0;i<G.vexnum;i++)
    {
        for(int j=0;j<G.vexnum;j++)
        {
            P[i][j]=G.matrix[i][j];
            D[i][j]=j;
        }
    }
    for(int k=0;k<G.vexnum;k++)
    {
        for(int i=0;i<G.vexnum;i++)
        {
            for(int j=0;j<G.vexnum;j++)
            {
                if(P[i][j]>(P[i][k]+P[k][j]))
                {
                    P[i][j]=P[i][k]+P[k][j];
                    D[i][j]=k;
                }
            }
        }
    }
}

int main()
{
    int start,end;
    Graph G;
    cout<<"cin vexnum"<<endl;
    cin>>G.vexnum;
    for(int i=0;i<G.vexnum;i++)
    {
        for(int j=0;j<G.vexnum;j++)
        {
            G.matrix[i][j]=INF;
        }
    }
    cout<<"cin edgenum"<<endl;
    cin>>G.edgenum;
    for(int i=0;i<G.edgenum;i++)
    {
        int v,w;
        cout<<"No."<<i+1<<endl;
        cout<<"cin start"<<endl;
        cin>>v;
        cout<<"cin end"<<endl;
        cin>>w;
        v--;
        w--;
        cout<<"cin value"<<endl;
        cin>>G.matrix[v][w];
        G.matrix[w][v]=G.matrix[v][w];
    }
    floyd(G,pMatrix,dMatrix);
    cout<<"cin start"<<endl;
    cin>>start;
    cout<<"cin end"<<endl;
    cin>>end;
    start--;
    end--;
    cout<<pMatrix[start][end];
    cout<<start<<"-->";
    while(dMatrix[start][end]!=end)
    {
        cout<<dMatrix[start][end]<<"-->";
        start=dMatrix[start][end];
    }
    cout<<end;
    return 0;
}

Dijstra

#include<iostream>
#include<windows.h>
#include<cstdio>
#define MAXN 10
#define INF 1000
using namespace std;
int arcs[MAXN][MAXN];
int preNode[MAXN];
int Dis[MAXN];
int flags[MAXN];
void ShortestPath_DIJ(int Num,int v0)
{
    for(int i=0;i<Num;i++)
    {
        flags[i]=0;
        preNode[i]=0;
        Dis[i]=arcs[v0][i];
        if(Dis[i]<INF)
            preNode[i]=v0;
    }
    Dis[v0]=0;
    flags[v0]=1;
    for(int i=0;i<Num;i++)
    {
        int min=INF;
        int loc;
        for(int j=0;j<Num;j++)
        {
            if(flags[j]!=1&&Dis[j]<min)
            {
                loc=j;
                min=Dis[j];
            }
        }
        flags[loc]=1;
        for(int j=0;j<Num;j++)
        {
            if(flags[j]!=1&&(min+arcs[loc][j])<Dis[j])
            {
                Dis[j]=min+arcs[loc][j];
            }
        }
    }
    for(int i=0;i<Num;i++)
    {
        cout<<Dis[i]<<" ";
    }
}
int main()
{
    int NodeNum;
    cout<<"cin NodeNum"<<endl;
    cin>>NodeNum;
    for(int i=0;i<NodeNum;i++)
    {
        for(int j=0;j<NodeNum;j++)
        {
            arcs[i][j]=INF;
        }
    }
    int temp;
    cout<<"cin EdgeNum"<<endl;
    cin>>temp;
    for(int i=0;i<temp;i++)
    {
        cout<<"No."<<i+1<<endl;
        int j,k;
        cin>>j>>k;
        j--;
        k--;
        cin>>arcs[j][k];
    }
    int v0;
    cout<<"cin v0"<<endl;
    cin>>v0;
    ShortestPath_DIJ(NodeNum,v0);
    return 0;
}

• 在看prim算法的时候，发现prim算法其实和dijstra算法十分的相似主要的区别体现在distance的更新上，dijstra中distance记录的是起点到各个节点的距离，prim算法中记录的则是已在树中的节点到其他节点的最短距离。