常用算法合集（一）

查找算法

顺序查找

#include <iostream>
using namespace std;

int SeqSearch2(int r[], int n, int k)
{
    int i=n;
    r[0]=k;
    while(r[i]!=k)
        i--;
    return i;
}

字符串匹配

BF算法

#include <iostream>
using namespace std;

int BF(char S[], char T[])
{
    int index=0;
    int i=0, j=0;
    while((S[i]!='\0')&&(T[j]!='\0'))
        if(s[i]==T[j]) {i++;j++;}
        else {index++; i=index; j=0;}
    if(T[j]=='\0') return index+1;
    else return 0;
}

KMP算法

#include <iostream>
#include <stdio.h>
using namespace std;

void GetNext(char T[], int next[])
{
    int i, j, len;
    for(j=0; T[j]!='\0'; j++)
    {
        for(len=j-1;len>=1; len--)
        {
            for(i=0; i<len; i++)
                if(T[i]!=T[j-len+i]) break;
            if(i==len)
            {
                next[j]=len;
                break;
            }
        }
        if(len<1) next[j]=0;
    }
}

int KMP(char S[], char T[])
{
    int i=0, j=0;
    int next[80];
    GetNext(T, next);
    while(S[i]!='\0'&&T[j]!='\0')
    {
        if(S[i]==T[j])
        {
            i++;
            j++;
        }
        else
        {
            i=next[j];
            if(j==-1)
            {
                i++;
                j++;
            }
        }
    }
    if(T[j]=='\0') return (i-strlen(T)+1);
    else return 0;
}

排序算法

选择排序

#include <iostream>
using namespace std;

void SelectSort(int r[], int n)
{
    int i, j, index, temp;
    for(i=0; i<n-1;i++)
    {
        index=i;
        for(j=i+1; j<n; j++)
            if(r[j]<r[index]) index=j;
        if(index!=i)
        {
            temp=r[i];
            r[i]=r[index];
            r[index]=temp;
        }
    }
}

起泡排序

#include <iostream>
using namespace std;

void BubbleSort(int r[], int n)
{
    int bound, exchange=n-1;
    while(exchange!=0)
    {
        bound=exchange; exchange=0;
        for(int j=0; j<bound; j++)
            if(r[j]>r[j+1])
            {
                int temp = r[j];
                r[j] = r[j+1];
                r[j+1] = temp;
                exchange = j;
            }
    }
}

归并排序

#include <iostream>
using namespace std;

void Merge(int r[], int r1[], int s, int m, int t)
{
    int i=s, j=m+1, k=s;
    while(i<=m&&j<=t)
    {
        if(r[i]<=r[j]) r1[k++]=r[i++];
        else r1[k++]=r[j++];
    }
    while(i<=m)
        r1[k++] = r[i++];
    while(j<=t)
        r1[k++] = r[j++];
}

void MergeSort(int r[], int s, int t)
{
    int m, r1[1000];
    if(s==t) return;
    else
    {
        m=(s+t)/2;
        MergeSort(r, s, m);
        MergeSort(r, m+1, t);
        Merge(r, r1, s, m, t);
        for(int i=s; i<=t; i++)
            r[i]=r1[i];
    }
}

快速排序

#include <iostream>
using namespace std;

void Partition(int r[], int first, int end)
{
    int i=first, j=end;
    while(i<j)
    {
        while(i<j&&r[i]<=r[j]) j--;
        if(i<j)
        {
            int temp=r[i];
            r[i]=r[j];
            r[j]=temp;
            i++;
        }
        while(i<j&&r[i]<r[j]) i++;
        if(i<j)
        {
            int temp=r[i];
            r[i]=r[j];
            r[j]=temp;
            j--;
        }
    }
    return i;
}

void QuickSort(int r[], int first, int end)
{
    int pivot;
    if(first<end)
    {
        pivot = Partition(r, first, end);
        QuickSort(r, first, pivot-1);
        QuickSort(r, pivot+1, end);
    }
}

最近对问题

#include <iostream>
using namespace std;

void ClosestPoints(int x[], int y[], int n)
{
    int index1, index2;
    int d, minDist=1000;
    for(int i=0; i<n-1; i++)
        for(int j=i+1; j<n; j++)
        {
            d=(x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]);
            if(d<minDist)
            {
                minDist=d;
                index1=i; index2=j;
            }
        }
    // 最近点对为 index1, index2 
    return minDist;
}

凸包问题

#include <iostream>
using namespace std;

void ConvexHull(int x[], int y[], int n)
{
    int i, j, k, sign1, sign2;
    int A, B, C;
    for(i=0; i<n-1; i++)
        for(j=i+1; j<n; j++)
        {
            sign1=0; sign2=0;
            A=y[i]-y[j]; B=x[j]-x[i];
            C=x[i]*y[j]-x[j]*y[i];
            for(k=0; k<n; k++)
            {
                if(k!=i&&k!=j)
                {
                    if(A*x[k]+B*y[k]+c>0) sign1=1;
                    else sign2=1;
                    if(sign1==sign2) break;
                }
            }
            //if(k==n)
            //  极点为(i,j) 
        }
}