#
快速排序(Quick Sort)其是速度最快的排序方式，时间复杂度为O(nlogn),最差情况下为O(n^2).由于O(nlogn)中的系数很小，所以很快，在实际中应用多。其是in place的排序方式，但是unstable（不稳定）
快速排序也是使用分而治之方法的应用，将任务分成子任务(divide)，然后解决子任务(conquer)，最后将结果组合起来。
其主要由2部分组成，partition(int p,int r)和quicksort(int p,int r).
其中quicksort(int p,int r)
{
if(p<r)
{
int q = parition(p,r);
quicksort(p,q-1);
quicksort(q+1,r);
}
}
而parition（int p,int r)函数只是选取一个pivot，然后将pivot将两部分分开。
具体的代码如下：
#include <iostream>
#include <algorithm>
#include <iterator>
#include <cstdlib>
#include <time.h>
#include <windows.h>
#define MAXSIZE 10000000
int arr[MAXSIZE];
using namespace std;
void print(bool flag=false)
{
if(flag)
{
copy(arr,arr+MAXSIZE,ostream_iterator<int>(cout," "));
cout<<endl;
}
}
void merge(int A[],int p,int q,int r)
{
int left = q-p+1;
int right = r-q;
int* L=new int[left];
int* R = new int[right];
int i,j,k;
for(i=0;i<left;i++)
L[i]=A[p+i];
for(j=0;j<right;j++)
R[j]=A[q+j+1];
for(k=0,i=0,j=0;(i<left)&&(j<right);k++)
{
if(L[i]<=R[j])
{
A[p+k]=L[i];
i++;
}
else
{
A[p+k]=R[j];
j++;
}
}
if(i<left)
{
for(;i<left;i++,k++)
A[p+k]=L[i];
}
if(j<right)
{
for(;j<right;j++,k++)
A[p+k]=R[j];
}
delete [] L;
delete [] R;
}
void mergesort(int A[],int p, int r)
{
if(p<r)
{
int q = (p+r)/2;
mergesort(A,p,q);
mergesort(A,q+1,r);
merge(A,p,q,r);
}
}
/*********************************
/**** Heap Sort Functions
/********************************/
void max_heapify(int i,int size)//size stands for heap size
{
int left = i<<1;
int right = left+1;
//get the largest of the i/left/right
int largest;
if((left<=size)&&(arr[left]>arr[i]))
{
largest = left;
}
else
largest = i;
if((right<=size)&&(arr[right]>arr[largest]))
largest = right;
//exchange the value of i and largest
if(i!=largest)
{
int temp =arr[i];
arr[i]=arr[largest];
arr[largest]=temp;
max_heapify(largest,size);
}
}
void build_max_heap()
{
int size = sizeof(arr)/sizeof(arr[0])-1;
for(int i=size/2;i>0;i--)
max_heapify(i,size);
}
void heapsort()
{
build_max_heap();
int size = sizeof(arr)/sizeof(arr[0])-1;
//int heapsize = size;
for(int i=size;i>1;i--)
{
int temp = arr[1];
arr[1]=arr[i];
arr[i]=temp;
//heapsize--;
max_heapify(1,i-1);
}
}
/***********************************
/*********** Quick Sort
/*********************************/
int partition(int p,int r)
{
int i=p-1;
int pivot = arr[r];
for(int j=p;j<=r;j++)
{
if(arr[j]<pivot)
{
i++;
int temp =arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
}
arr[r]=arr[i+1];
arr[i+1]=pivot;
return i+1;
}
void quicksort(int p,int r)
{
if(p<r)
{
int q = partition(p,r);
quicksort(p,q-1);
quicksort(q+1,r);
}
}
int main(int argc,char* argv[])
{
int size = MAXSIZE;
for(int i=0;i<size;i++)
{
arr[i] = rand()%MAXSIZE;
}
print();
DWORD start = timeGetTime();
//mergesort(arr,0,MAXSIZE-1);
//heapsort();
quicksort(0,MAXSIZE-1);
DWORD end = timeGetTime();
print();
cout<<end-start<<endl;
system("pause");
return 0;
}
堆排序(heap sort)应用的是堆数据结构来实现的排队算法
主要是由3部分组成:
max_heapify主要是来维持max heap的数据结构，其算法复杂度为O(lgn)【应用master定理的第二条来得到】
build_max_heap，从整个堆数列长度length的1/2开始到1，进行调用max_heapify函数得到，其算法复杂度为O(n)
heap_sort首先是调用build_max_heap，来构造一大堆，然后再将arr[1]和堆最大长度进行更换，将堆长度减一，再调用max_heapify来完成了排序功能，算法复杂度为O(nlogn)
主要代码实现为:
#include <iostream>
#include <algorithm>
#include <iterator>
#include <cstdlib>
#include <time.h>
#include <windows.h>
#define MAXSIZE 100
int arr[MAXSIZE];
using namespace std;
void print(bool flag=true)
{
if(flag)
{
copy(arr,arr+MAXSIZE,ostream_iterator<int>(cout," "));
cout<<endl;
}
}
void merge(int A[],int p,int q,int r)
{
int left = q-p+1;
int right = r-q;
int* L=new int[left];
int* R = new int[right];
int i,j,k;
for(i=0;i<left;i++)
L[i]=A[p+i];
for(j=0;j<right;j++)
R[j]=A[q+j+1];
for(k=0,i=0,j=0;(i<left)&&(j<right);k++)
{
if(L[i]<=R[j])
{
A[p+k]=L[i];
i++;
}
else
{
A[p+k]=R[j];
j++;
}
}
if(i<left)
{
for(;i<left;i++,k++)
A[p+k]=L[i];
}
if(j<right)
{
for(;j<right;j++,k++)
A[p+k]=R[j];
}
delete [] L;
delete [] R;
}
void mergesort(int A[],int p, int r)
{
if(p<r)
{
int q = (p+r)/2;
mergesort(A,p,q);
mergesort(A,q+1,r);
merge(A,p,q,r);
}
}
/*********************************
/**** Heap Sort Functions
/********************************/
void max_heapify(int i,int size)//size stands for heap size
{
int left = i<<1;
int right = left+1;
//get the largest of the i/left/right
int largest;
if((left<=size)&&(arr[left]>arr[i]))
{
largest = left;
}
else
largest = i;
if((right<=size)&&(arr[right]>arr[largest]))
largest = right;
//exchange the value of i and largest
if(i!=largest)
{
int temp =arr[i];
arr[i]=arr[largest];
arr[largest]=temp;
max_heapify(largest,size);
}
}
void build_max_heap()
{
int size = sizeof(arr)/sizeof(arr[0])-1;
for(int i=size/2;i>0;i--)
max_heapify(i,size);
}
void heapsort()
{
build_max_heap();
int size = sizeof(arr)/sizeof(arr[0])-1;
int heapsize = size;
for(int i=size;i>1;i--)
{
int temp = arr[1];
arr[1]=arr[i];
arr[i]=temp;
heapsize--;
max_heapify(1,heapsize);
}
}
int main(int argc,char* argv[])
{
int size = MAXSIZE;
for(int i=0;i<size;i++)
{
arr[i] = rand()%MAXSIZE;
}
print();
DWORD start = timeGetTime();
//mergesort(arr,0,MAXSIZE-1);
heapsort();
DWORD end = timeGetTime();
print();
cout<<end-start<<endl;
system("pause");
return 0;
}
归并排序(Merge Sort)，是非常好的一种排序方式。时间复杂度为O（nlogn)。空间复杂度为O(n)
同快速排序相比，其有稳定性以及最差情况下为O(nlogn)等特点。
归并排序是典型的分而治之方法，首先将排序任务分成自任务，即Divide过程，然后将各个子任务初步完成(Conquer)，最后将所有的子任务合并(merge)就完成了整个任务。
整个算法框架如下：
void mergesort(int A[],int p,int r)
{
if(p<r)
{
int q=(p+r)/2;
mergesort(A,p,q);
mergesort(A,q+1,r);
merge(A,p,q,r);
}
}
在merge中，首先将p->q的(q-p+1)个放到一个左边的数组L中，将q+1->r的(r-q)个放到右边的数组R中，然后将数组L和数组R的数按顺序放置到A中。
void merge(A,p,q,r)
{
//construct the L and R array
int left=q+1-p;
int right = r-q;
int* L=new int[left];
int* R = new int[right];
//fill the L and R array
int i,j,k;
for(i=0;i<left;i++)
L[i]=A[p+i];
for(j=0;j<right;j++)
R[j]=A[q+j+1];
//copy the value from L and R to A
//Notice there are three cases
for(k=0,i=0,j=0;(i<left)&&(j<right);k++)
{
if(L[i]<=R[j])
{
A[p+k]=L[i];
i++;
}
else
{
A[p+k]=R[j];
j++;
}
}
if(i<left)
{
for(;i<left;i++,k++)
A[p+k]=L[i];
}
if(j<right)
{
for(;j<right;j++,k++)
A[p+k]=R[j];
}
//delete the L and R
delete [] L;
delete [] R;
}
整个mergesort的可执行代码如下：
#include <iostream>
#include <algorithm>
#include <iterator>
#include <cstdlib>
#include <time.h>
#include <windows.h>
#define MAXSIZE 100
int arr[MAXSIZE];
using namespace std;
void print(bool flag=true)
{
if(flag)
{
copy(arr,arr+MAXSIZE,ostream_iterator<int>(cout," "));
cout<<endl;
}
}
void merge(int A[],int p,int q,int r)
{
int left = q-p+1;
int right = r-q;
int* L=new int[left];
int* R = new int[right];
int i,j,k;
for(i=0;i<left;i++)
L[i]=A[p+i];
for(j=0;j<right;j++)
R[j]=A[q+j+1];
for(k=0,i=0,j=0;(i<left)&&(j<right);k++)
{
if(L[i]<=R[j])
{
A[p+k]=L[i];
i++;
}
else
{
A[p+k]=R[j];
j++;
}
}
if(i<left)
{
for(;i<left;i++,k++)
A[p+k]=L[i];
}
if(j<right)
{
for(;j<right;j++,k++)
A[p+k]=R[j];
}
delete [] L;
delete [] R;
}
void mergesort(int A[],int p, int r)
{
if(p<r)
{
int q = (p+r)/2;
mergesort(A,p,q);
mergesort(A,q+1,r);
merge(A,p,q,r);
}
}
int main(int argc,char* argv[])
{
int size = MAXSIZE;
for(int i=0;i<size;i++)
{
arr[i] = rand()%MAXSIZE;
}
print();
DWORD start = timeGetTime();
mergesort(arr,0,MAXSIZE-1);
DWORD end = timeGetTime();
print();
cout<<end-start<<endl;
system("pause");
return 0;
}
前面给出了插入排序，其基于插入牌的机制
下面给出选择排序和冒泡排序的原理和实现
选择排序：
就是从后面的部分选择最小值(或者最大值）来代替前者，核心算法为：
for(int i=0;i<size;i++)
{
//assume the smallest value is at size-1
int temp = arr[size-1];
int index = size-1;
//compare the rest(from i--->size-1)
for(j=i;j<size-1;j++)
{
if(arr[j]<temp)
{
temp = arr[j];
index = j;
}
}
//exchange the value
if(index!=i)
{
arr[index]=arr[i];
arr[i]=temp;
}
}
具体代码实现为：
#include <iostream>
#include <algorithm>
#include <iterator>
using namespace std;
int main(int argc,char* argv[])
{
int arr[]={5,6,1,2,7,3,8,10,4,9};
int size = sizeof(arr)/sizeof(arr[0]);
copy(arr,arr+size,ostream_iterator<int>(cout," "));
cout<<endl;
for(int i=0;i<size;i++)
{
int temp = arr[size-1];
int index = size-1;
for(int j=i;j<size-1;j++)
{
if(arr[j]<temp)
{
temp = arr[j];
index = j;
}
}
if(i!=index)
{
arr[index]=arr[i];
arr[i]=temp;
}
}
copy(arr,arr+size,ostream_iterator<int>(cout," "));
cout<<endl;
system("pause");
return 0;
}
冒泡算法主要是从后面开始往上面进行冒泡，需要冒泡的话，必须要相邻的元素之间进行比较，其实现代码如下:
#include <iostream>
#include <algorithm>
#include <iterator>
using namespace std;
int main(int argc,char* argv[])
{
int arr[]={5,6,1,2,7,3,8,10,4,9};
int size = sizeof(arr)/sizeof(arr[0]);
copy(arr,arr+size,ostream_iterator<int>(cout," "));
cout<<endl;
for(int i=0;i<size;i++)
for(int j=size-1;j>i;j--)
{
if(arr[j]<arr[j-1])
{
int temp = arr[j];
arr[j]=arr[j-1];
arr[j-1]=temp;
}
}
copy(arr,arr+size,ostream_iterator<int>(cout," "));
cout<<endl;
system("pause");
return 0;
}
常见的排序方式有6种：
---简单排序里面的有：插入排序、选择排序、冒泡排序，时间复杂度为O(n^2)
---线性对数阶的排序: 归并排序(merge sort),快速排序，堆排序，时间复杂度为O(nlogn)
在n<=50的情况下，最好使用插入排序或者选择排序，由于选择排序移动次数比插入排序少，在数据量比较多的情况，推荐使用选择排序。
如果序列基本上正序了，则使用插入排序、冒泡排序或者随机的快速排序
在n非常大的情况下，使用O(nlogn)的算法，即归并排序、快速排序、堆排序。后2者是不稳定的排序，而merge排序是稳定的排序方式，快速排序是基于比较的排序中的最好的排序方法。
实验条件下算法运行时间：（单位毫秒，10万随机数）
冒泡排序: 56953
选择排序: 20109
插入排序: 14547
归并排序: 134
堆排序: 67
快速排序: 28
三种O(nlogn)的排序时间比较为：
排序算法 10万 100万 1000万
归并排序 134 1309 13985
堆排序 67 865 14292
快速排序 28 513 9815
下面给出insertion sort的原理和实现
insertion sort是稳定排序，在数据量非常小的情况下，非常快速。其原理就如同打牌的时候按顺序插入牌一样(来自introdution to algorithm)，从后面往前面找大于最新的牌的数，然后往后面替换，再将最新的牌插入进去完成了前面的牌是已经排序好的。核心算法如下：
for(int i=1;i<size;i++)
{
//get the new card
int temp = arr[i];
int j=i-1;
while((j>=0)&&(arr[j]>temp))//find the old card bigger than the new card
{
arr[j+1]=arr[j];
j--;
}
//get the position of the new card
arr[j+1]=temp;
}
具体实现为:
#include <iostream>
#include <algorithm>
#include <iterator>
using namespace std;
int main(int argc,char* argv[])
{
int arr[]={5,6,1,2,7,3,8,10,4,9};
int size = sizeof(arr)/sizeof(arr[0]);
copy(arr,arr+size,ostream_iterator<int>(cout," "));
cout<<endl;
for(int i=1;i<size;i++)
{
int temp = arr[i];
int j=i-1;
while((arr[j]>temp)&&(j>=0))
{
arr[j+1]=arr[j];
j--;
}
arr[j+1]=temp;
}
copy(arr,arr+size,ostream_iterator<int>(cout," "));
cout<<endl;
system("pause");
return 0;
}
过去一直用的求素数的方法为:
bool isPrime(const int n)
{
for(int i=2;i<=sqrt(n);i++)
if((n%i)==0)
return false;
return true;
}
但是用这种方法求从2-->n的素数的话，时间复杂度高。
今天发现一种新的方法，效率提高了很多，其核心思想如下：
bool* prime = new bool[n];
for(int i=0;i<n;i++)
prime[i]=true;
for(int i=2;i<=sqrt(n);i++)
{
if(prime[i])
{
for(int j=i*i;j<=n;j++)
prime[j]=false;
}
}
整个测试代码如下：
#include <iostream>
#include <string>
#include <cmath>
#include <ctime>
#include <windows.h>
using namespace std;
bool* sieve(int n)
{
bool* prime = new bool[n];
for(int i=0;i<n;i++)
prime[i]=true;
prime[0]=false;
prime[1]=false;
double maxsqrt=sqrt((double)n);
for(int i=2;i<=maxsqrt;i++)
{
if(prime[i])
{
for(int j=i*i;j<=n;j+=i)
prime[j]=false;
}
}
return prime;
}
int main(int argc,char* argv[])
{
int n;
while(1)
{
cin>>n;
if(n==0)
break;
DWORD start = timeGetTime();
for(int i=3;i<=n;i++)
{
bool flag = true;
for(int j=2;j<=sqrt(i);j++)
{
if(!(i%j))
{
flag = false;
break;
}
}
/*
if(flag)
cout<<i<<" ";
*/
}
DWORD median = timeGetTime();
bool* prime = sieve(n);
/*
for(int i=0;i<n;i++)
if(prime[i])
cout<<i<<" ";
*/
DWORD end = timeGetTime();
cout<<endl;
cout<<(median-start)<<" ms "<<(end-median)<<" ms"<<endl;
delete prime;
}
system("pause");
return 0;
}
由于有限自动机方法与KMP算法类似，并且有限自动机方法在预处理上的时间复杂度比KMP方法高，所以在本文的讨论中，暂时不讨论有限自动机方法，主要是考虑KMP算法。
KMP算法是一个非常有名的字符串匹配算法，其由Knuth,Morris和Pratt一起提出来的，预处理时间为O(m),其中m为匹配字符串的长度，匹配时间为O(n)，其中n为需要匹配的字符串的长度。
核心算法如下：
//预处理部分
int pi[m];
pi[0]=0;
int k = 0;
for(int i=1;i<m;i++)
{
while((k>0)&&(p[i]!=p[k])
k=pi[k];
if(p[i]==p[k])
k++;
pi[i]=k;
}
//匹配部分
int k=0;
for(int i=0;i<n;i++)
{
while((k>0)&&(p[k]!=t[i]))
k=pi[k];
if(p[k]==t[i])
k++;
if(k==m)
{
//输出结果，从(i+1-m)开始已经匹配
k=pi[m-1];//开始下一个匹配
}
}
具体的可运行的实现代码为：
1 #include <iostream>
2 #include <string>
3
4 using namespace std;
5
6 int main(int argc,char* argv[])
7 {
8 char *t=NULL,*p=NULL;
9 int *pi=NULL;
10 string text,pattern;
11
12 while(1)
13 {
14 cin>>text>>pattern;
15 int n = text.length();
16 int m = pattern.length();
17
18 //t= new char[n+1];
19 //p= new char[m+1];
20 t= new char[n];
21 p= new char[m];
22 pi = new int[m];
23
24 //strcpy(t,text.c_str());
25 //strcpy(p,pattern.c_str());
26 memcpy(t,text.data(),n);
27 memcpy(p,pattern.data(),m);
28
29 //calculate the PI array
30 int q = 0;
31 pi[0]=0;
32
33 for(int i=1;i<m;i++)
34 {
35 while((q>0)&&(p[q]!=p[i]))
36 {
37 q=pi[q];
38 }
39
40 if(p[q]==p[i])
41 q++;
42
43 pi[i]=q;
44 }
45
46 //use the KMP matching algorithm
47 q = 0;
48 for(int i=0;i<n;i++)
49 {
50 while((q>0)&&(p[q]!=t[i]))
51 {
52 q = pi[q];
53 }
54
55 if(p[q]==t[i])
56 q++;
57
58 if(q==m)
59 {
60 cout<<((i+1)-m)<<endl;
61 q = pi[m-1];
62 }
63 }
64
65 delete[] t;
66 delete[] p;
67 delete[] pi;
68 }
69
70 system("pause");
71 return 0;
72 }
73
前面已经说到了naive的方法来匹配字符串，但是该方法的特点是复杂度高，未能充分利用计算得到的值作为下一步计算的结果，因此，复杂度相当比较高。
Rabin-Karp提出了新的字符串匹配方法：
Rabin-Karp方法主要是分2部分：
(1)预处理(pre-processing)
对pattern字符串的m个进行计算，得到其hash值。 复杂度为O(m)
(2)匹配(matching)
for(int i=0;i<n-m;i++)
{
计算t[i..i+m]的hash值。
再同pattern字符串的hash值进行对比，如果相同，则使用naive办法，继续一个字符一个字符地比较。
使用Horner法则计算下一个m字符的hash值。(即h(s+1)=f(h(s))).
}
整个算法的复杂度：
在最差的情况下，复杂度为O(m)+O(m*(n-m+1))
期望的情况为O(n-m+1+cm)=O(n+m).
实验代码如下：（暂时只是考虑支持12345678901234567890 匹配 234等的情况）
1 #include <iostream>
2 #include <string>
3
4 using namespace std;
5
6 #define Q 997 //Should be a prime
7 #define D 10 //|sizeof character set|
8
9 inline int geth(int m)//h=d^(m-1)%q
10 {
11 int len=1;
12 for(int i=0;i<(m-1);i++)
13 {
14 len*=D;
15 }
16 return len%Q;
17 }
18
19 int main(int argc,char* argv[])
20 {
21 char *t=NULL,*p=NULL;
22 string text,pattern;
23 int h,p0=0,t0=0;
24
25 while(1)
26 {
27 int index = 0;
28
29 cin>>text>>pattern;
30 int n = text.length();
31 int m = pattern.length();
32
33 //t= new char[n+1];
34 //p= new char[m+1];
35 t= new char[n];
36 p= new char[m];
37
38 h = geth(m);
39 p0=t0=0;
40
41 //strcpy(t,text.c_str());
42 //strcpy(p,pattern.c_str());
43 memcpy(t,text.data(),n);
44 memcpy(p,pattern.data(),m);
45
46 for(int i=0;i<m;i++)//get the initial value from pattern and text
47 {
48 p0 =(D*p0+(p[i]-'0'))%Q;
49 t0 = (D*t0+(t[i]-'0'))%Q;
50 }
51
52 for(int i=0;i<(n-m);i++)
53 {
54 if(p0==t0)//should call the naive algorithm to check whether the two string is the same
55 {
56 bool match = true;
57 for(int j=0;j<m;j++)
58 {
59 if(p[j]!=t[i+j])
60 match = false;
61 }
62
63 if(match)
64 cout<<i<<endl;
65 }
66
67 t0 = ((D*(t0-(t[i]-'0')*h)+t[i+m])-'0')%Q;
68 }
69
70 delete[] t;
71 delete[] p;
72 }
73
74 system("pause");
75 return 0;
76 }
77
作者: kingoal
给定一个输入的字符串t(text)，长度为n(n=strlen(t))，给出匹配模式p(pattern)，长度为m(m=strlen(p)).
在Introduction to algorithm书(CLRS)中，字符串算法主要是讨论了4种，分别对应的是：
朴素(Naive) ----------O(m*(n-m+1))
Rabin-Karp-----------O(m*(n-m+1))
有限自动机-----------O(n)
Knuth-Morris-Pratt------------------O(n)
下面分4部分具体介绍该4种字符串匹配算法。
Naive算法非常简单，就是将t的字节从0到n-m+1来一一匹配p的m个字符，若所有的m字符都匹配成功，则输出匹配成功，输出当前的index值。
下面给出Naive的实现代码：
1 #include <iostream>
2 #include <string>
3
4 using namespace std;
5
6 int main(int argc,char* argv[])
7 {
8 char *t=NULL,*p=NULL;
9 string text,pattern;
10
11 while(1)
12 {
13 int index = 0;
14
15 cin>>text>>pattern;
16 int n = text.length();
17 int m = pattern.length();
18
19 //t= new char[n+1];
20 //p= new char[m+1];
21 t= new char[n];
22 p= new char[m];
23
24 //strcpy(t,text.c_str());
25 //strcpy(p,pattern.c_str());
26 memcpy(t,text.data(),n);
27 memcpy(p,pattern.data(),m);
28
29 for(int i=0;i<n-m+1;i++)
30 {
31 bool match=true;
32
33 for(int j=0;j<m;j++)
34 {
35 if(t[i+j]!=p[j])
36 match=false;
37 }
38 if(match)
39 cout<<index<<endl;
40
41 index++;
42 }
43
44 delete[] t;
45 delete[] p;
46 }
47
48 system("pause");
49 return 0;
50 }
51