常用算法合集（一）
查找算法
顺序查找
#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]!=' ')&&(T[j]!=' '))
if(s[i]==T[j]) {i++;j++;}
else {index++; i=index; j=0;}
if(T[j]==' ') 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]!=' '; 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]!=' '&&T[j]!=' ')
{
if(S[i]==T[j])
{
i++;
j++;
}
else
{
i=next[j];
if(j==-1)
{
i++;
j++;
}
}
}
if(T[j]==' ') 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)
}
}