算法集锦(四)
歸并排序
?
歸并排序算法實現：
#include<stdio.h> #include<stdlib.h> #define FatalError( Str ) fprintf( stderr, "%s\n", Str ), exit( 1 ) typedef int ElementType;void Merge(ElementType A[],ElementType TmpArray[],int lpos,int rpos,int rightend) { int i,leftend,NumElements,TmpPos; leftend=rpos-1; TmpPos=lpos; NumElements=rightend-lpos+1; while(lpos<=leftend&&rpos<=rightend) { if(A[lpos]<=A[rpos]) TmpArray[TmpPos++]=A[lpos++]; else TmpArray[TmpPos++]=A[rpos++]; } while(lpos<=leftend) TmpArray[TmpPos++]=A[lpos++]; while(rpos<=rightend) TmpArray[TmpPos++]=A[rpos++]; //由于每次將臨時數組中的元素復制回原來數組時，不能從第一個開始復制，只是從剛剛合并的那一部分復制，所以記錄要合并的長度 for(i=0;i<NumElements;i++,rightend--) A[rightend]=TmpArray[rightend]; } void Msort(ElementType A[],ElementType TmpArray[],int left,int right) { int Center; if(left<right) { Center=(left+right)/2; Msort(A,TmpArray,left,Center); Msort(A,TmpArray,Center+1,right); Merge(A,TmpArray,left,Center+1,right); } } void MergeSort(ElementType A[],int N) { ElementType *TmpArray; TmpArray=malloc(sizeof(ElementType)*N); if(TmpArray!=NULL) { Msort(A,TmpArray,0,N-1); free(TmpArray); } else FatalError("No space for tmp array[]"); } void Print(int A[],int N) { int i; for(i=0;i<N;i++) printf(" %d ",A[i]); } int main() { int arr[10]={2,87,39,49,34,62,53,6,44,98}; Print(arr,10); printf("\n"); MergeSort(arr,10); Print(arr,10); printf("\n"); return 0; }運行結果如下：
?
?
快速排序算法-C語言實現
注：本篇內容為翻譯，之所以選擇這篇進行翻譯原因是該文章含有動畫，能夠更加直觀地展示快速排序。同時，可以仔細看一下代碼，代碼中把結構化的思想給予了更加充分地表現。按照功能進行模塊劃分的思想得到了徹底地貫徹。
?
以下內容翻譯自：
?
?
?
譯文：
在快速排序算法中，使用了分治策略。首先把序列分成兩個子序列，遞歸地對子序列進行排序，直到整個序列排序結束。
?
步驟如下：
?
在序列中選擇一個關鍵元素做為軸；
?
對序列進行重新排序，將比軸小的元素移到軸的前邊，比軸大的元素移動到軸的后面。在進行劃分之后，軸便在它最終的位置上；
?
遞歸地對兩個子序列進行重新排序：含有較小元素的子序列和含有較大元素的子序列。
?
下面的動畫展示了快速排序算法的工作原理。
?
快速排序圖示：可以圖中在每次的比較選取的key元素為序列最后的元素。
?
#include <stdio.h> #include <stdlib.h> void swap(int *x,int *y) {int temp; temp = *x; *x = *y; *y = temp; } int choose_pivot(int i,int j ) { return((i+j) /2); } void quicksort(int list[],int m,int n) { int key,i,j,k; if( m < n) { k = choose_pivot(m,n); swap(&list[m],&list[k]); key = list[m]; i = m+1; j = n; while(i <= j) { while((i <= n) && (list[i] <= key)) i++; while((j >= m) && (list[j] > key)) j--; if( i < j) swap(&list[i],&list[j]); } // 交換兩個元素的位置 swap(&list[m],&list[j]); // 遞歸地對較小的數據序列進行排序 quicksort(list,m,j-1); quicksort(list,j+1,n); } } void printlist(int list[],int n) { int i; for(i=0;i<n;i++) printf("%d\t",list[i]); } void main() { const int MAX_ELEMENTS = 10; int list[MAX_ELEMENTS]; int i = 0; // 產生填充序列的隨機數 for(i = 0; i < MAX_ELEMENTS; i++ ){ list[i] = rand(); } printf("進行排序之前的序列:\n"); printlist(list,MAX_ELEMENTS); // sort the list using quicksort quicksort(list,0,MAX_ELEMENTS-1); // print the result printf("使用快速排序算法進行排序之后的序列:\n"); printlist(list,MAX_ELEMENTS); }?
?
改進版的快速排序
#include<stdio.h>
#include<stdlib.h>
typedef int ElementType;
#define Cutoff (3)
void swap(int *a,int *b)
{
int temp=*a;
*a=*b;
*b=temp;
}
void WithSentrySort(ElementType A[],int N)
{
int i,j;
for(i=2;i<N;i++)
{
A[0]=A[i];
for(j=i-1;A[j]>A[0];j--)
{
A[j+1]=A[j];
}
A[j+1]=A[0];
}
}
ElementType Median3(ElementType A[], int Left, int Right)
{
int Center = (Left + Right) / 2;
if (A[Left] > A[Center])
swap(&A[Left], &A[Center]);
if (A[Left] > A[Right])
swap(&A[Left], &A[Right]);
if (A[Center] > A[Right])
swap(&A[Center], &A[Right]);
swap(&A[Center], &A[Right - 1]);
return A[Right - 1];
}
void QSort(ElementType A[], int Left, int Right)
{
int i, j;
ElementType Pivot;
if (Left + Cutoff <= Right){
Pivot = Median3(A, Left, Right);
i = Left; j = Right - 1;
for (;;){
while (A[++i] < Pivot);
while (A[--j] > Pivot);
if (i < j)
swap(&A[i], &A[j]);
else
break;
}
swap(&A[i], &A[Right - 1]);
QSort(A, Left, i - 1);
QSort(A, i + 1, Right);
}
else
WithSentrySort(A + Left, Right - Left + 1);
}
void QuickSort(ElementType A[], int N)
{
QSort(A, 0, N -1);
}
void Print(int A[],int n)
{
int i;
for(i=0;i<n;i++)
printf("%d ",A[i]);
printf("\n");
}
int main()
{
const int MAX_ELEMENTS=10;
int list[MAX_ELEMENTS];
int i=0;
for(i=0;i<MAX_ELEMENTS;i++)
list[i]=rand();
printf("排序之前：");
Print(list,MAX_ELEMENTS);
QuickSort(list,MAX_ELEMENTS);
printf("排序之后：");
Print(list,MAX_ELEMENTS);
return 0;
}
運行結果：
?
?
不相交集（The Disjoint Set ADT）
0）引論
不相交集是解決等價問題的一種有效的數據結構，之所以稱之為有效是因為，這個數據結構簡單（幾行代碼，一個簡單數組就可以搞定），快速（每個操作基本上可以在常數平均時間內搞定）。
首先我們要明白什么叫做等價關系，而在這個之前要先有一個關系（relation）的定義
Relation：定義在數據集S上的關系R是指，對于屬于數據集S中的每一對元素（a，b），a R b要么是真要么是假。如果a R b為真，就說a related b，即a與b相關。
等價關系也是一種關系（Relation），只不過是要滿足一些約束條件
a）?a R a，對于所有屬于S的a
b）?a R b 當且僅當 b?R a
c）?a R b 并且 b?R a 意味著?a R c
動態等價性問題：
定義在非空集合S上的關系R，對于任意屬于數據集S中的每一對元素（a，b），確定a R b是否為真，也就是說a與b是否有關系。
而對于a與b是否有關系，我們只需要證明a與b是否在同一個等價類集合中。
?
?
1）基本結構
Find操作：返回給定元素的集合的名字，也就是檢查a，b是否在同一個等價類中。對于Find運算，最重要的是判斷Find（a，S） ==?Find（b，S）是否成立。
Union操作：如果a，b不在一個等價類中，可以用Union操作把這連個等價類合并為一個等價類。
我們可以用tree結構來表示一個集合，root可以表示集合的名字。由于僅有上面的兩個操作而沒有順序信息，因此我們可以將所有的元素用1-N編號，編號可以用hashing方法。
?
進一步可以發現對于這兩個操作無法使其同時達到最優，也就是說當Find以常數最壞時間運行時，Union操作會很慢，同理顛倒過來。因此就有了2種實現方式。
a）使Find運行快
在數組中保存每個元素的等價類的名字，將所有等價類的元素放到一個鏈表中
b）使Union運行快
使用樹來表示每一個集合，根節點表示集合的名字。數組元素P[i]表示元素i的父親，若i為root，則P[i]=0。
對于Union操作，相當于把連個樹合并，也就是指針的移動，如下圖所示：
?
typedef int DisjSet[NumSets+1]; typedef int SetType;void initialize(DisjSet S) { int i; for(i=NumSets;i>0;i--) s[i]=0; } void SetUnion(DisjSet S, SetType Root1, SetType Root2) { S[Root2] = Root1; } SetType Find(ElementType X, DisjSet S) { if(S[x]<=0) return x; else return Find(S[x],S); }對于Find操作就是一個不斷返回父節點知道找到根節點的遞歸過程。
?
?
2）靈巧合并算法
上面的合并算法相當隨意，它就是把第二棵樹作為第一棵樹的子樹來完成合并操作。有一個簡單的改進方法是總是讓較小的樹成為較大的樹的子樹，這種方法叫做Union-by-Size，如下圖所示Union-by-Size可以降低樹的深度，每個節點的深度都不會超過O(logN)。
為了實現這種方法，必須記錄每一棵樹的大小。我們可以另每一個根節點的數組元素表示樹的大小的賦值，非根節點不變，依舊表示其父節點。這其實是把上面方法的數組中的0的位置做了一些利用。
?
另一種方法是Union-by-Height，也就是說我們把高度較淺的樹作為高度較深的樹的子樹。亦即根節點記錄的是樹的高度的負值。
?
Union-by-Height的Union代碼實現
void SetUnion(DisjSet S, SetType Root1, SetType Root2) {//add the low height tree to the high height tree.if(S[Root2]<S[Root1]) S[Root1] = Root2; else { if(S[Root1] = S[Root2]) //same height S[Root1]--; S[Root2] = Root1; } }3）路徑壓縮
?
隨著樹的加深，Find操作的時間會增加。如果Find操作比Union操作多的多的話，那么運算時間會相當糟糕，比快速查找還要差。而且從上面可以看出，Union算法的改進比較困難，因此我們應該嘗試去使Find更加高效。這就引入了path compression。
路徑壓縮：在Find操作期間執行與Union操作無關，路徑壓縮的效果是從X到根節點的路徑上的每一個結點都使它的父節點成為根節點。
?
代碼實現：
SetType Find(ElementType X, DisjSet S) { if(S[x]<=0) return x; else return S[x] = Find(S[x],S); }和上面相比，代碼只有一點點小修改。
?
路徑壓縮算法是與Union-by-Size相兼容的，與Union-by-Height并不完全兼容。
?
?
4）小應用
說了這么多，這個數據結構總要有點用處啊，否則就沒有什么意義了。
一個例子是計算機網絡和雙向連接表，每一個連接將文件從一個計算機傳遞到另一個計算機。現在的問題是能否將文件從任意一個計算機傳遞到另一個任意的計算機，并且這個問題要on-line解決。
解決這個問題，就可以用到上面的數據結構。開始階段我們可以把每一臺計算機放到他自己的集合中，要求兩臺計算機傳遞文件當且僅當這兩臺計算機在同一個集合中。因此傳輸文件能力相當于一個等價關系。當我們需要傳輸文件時，檢驗兩個計算機是否在同一個集合里，是的話就傳輸文件，否的話，就用Union方法把它們合并到一個集合中，然后傳輸文件。
?
?
5）總結
不相交集是一個非常簡單的數據結構，僅用幾行代碼就可以搞定。對于Find操作，重要的是Find（a，S） ==?Find（b，S）為真還是假。Union操作有很多種實現，比較靈活。為了節省Find操作的時間，引入了路徑壓縮算法，這是自調整（self-adjustment）的最早形式之一。
總結
- 上一篇： Grpc+Grpc Gateway实践一
- 下一篇： 【转】ubuntu 下安装mongodb