#
快速排序(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