常用算法合集（一）
目录
查找算法
顺序查找
#include
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
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
#include
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
排序算法
选择排序
#include
using namespace std;
void SelectSort(int r[], int n)
{
int i, j, index, temp;
for(i=0; i
起泡排序
#include
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; jr[j+1])
{
int temp = r[j];
r[j] = r[j+1];
r[j+1] = temp;
exchange = j;
}
}
}
归并排序
#include
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
using namespace std;
void Partition(int r[], int first, int end)
{
int i=first, j=end;
while(i
最近对问题
#include
using namespace std;
void ClosestPoints(int x[], int y[], int n)
{
int index1, index2;
int d, minDist=1000;
for(int i=0; i
凸包问题
#include
using namespace std;
void ConvexHull(int x[], int y[], int n)
{
int i, j, k, sign1, sign2;
int A, B, C;
for(i=0; i0) sign1=1;
else sign2=1;
if(sign1==sign2) break;
}
}
//if(k==n)
// 极点为(i,j)
}
}