搜尋的方法：
1. Linear Search – 線性搜尋
2. Binary Search – 二分法搜尋
3. Fibonacci Search – 費氏搜尋
4. Interploation Search – 插補搜尋
Linear Search
線性搜尋
作法：從頭到尾依照資料順序一筆筆比對搜尋。
時間複雜度：O(n)平均比較次數(n+1)/2
優點：支援循序隨機存取資料，紀錄可不用先行排序。
Binary Search Tree
二元搜尋樹
需要先排序，需先把資料由小到大排好。需要隨機隨取支援，意味只能使用陣列實做，不能使用鏈結。
作法：比中間值大往右搜尋，比中間值小往左搜尋。
二元搜尋樹搜尋演算法
BST Search algorithm
void BSTSearch(T,X)
{
if (T=null)
printf("Not Found");
else if T->data=X
printf("Found");
else if T->data>X
BSTSearch(T->Lchild,X);
else
BSTSearch(T->Rchild,X);
}
二元搜尋樹插入演算法
BST Insert algorithm
void BSTInsert(T,X)
{
if (T=null)
temp=new treepointer;
temp->data=X;
temp->Lchild=null;
temp->Rchild=null;
T=temp;
else if T->data>X
BSTInsert(T->Lchild,X);
else
BSTInsert(T->Rchild,X);
}
Binary Search Decision Tree
二元搜尋決策樹
Decision的建立為Root必為該段中間值。
Sort排序
依存放方式可以分成兩種：
內部排序：排序資料置於Memory中來處理。
外部排序：資料量大，須經由Memory與Disk之間處理之。
依結果可以分成：
穩定的排序法（stable）：不會進行沒有必要的交換步驟。
不穩定的排序法（unstable）：會進行沒有必要的交換步驟。
各種排序法的比較
| 排序法/狀況 | 平均狀況 | 最差情況 | 額外空間 | 穩定排序法 |
| 插入排序法 | O(N^2) | O(N^2) | O(1) | YES |
| 選擇排序法 | O(N^2) | O(N^2) | O(1) | NO |
| 氣泡排序法 | O(N^2) | O(N^2) | O(1) | YES |
| 快速排序法 | O(N log2 N) | O(N^2) | O(log2 N) | NO |
| 合併排序法 | O(N log2 N) | O(N log2 N) | O(N) | YES |
| 堆積排序法 | O(N log2 N) | O(N log2 N) | O(1) | NO |
說明：上面三種為初等排序法，下面三種為高等排序法
（這張表必須記憶，除非你有把握短時間推算）
Insertion Sort（插入排序法）
作法：將第i項資料插入到前面（i-1）項已排好的紀錄中，使得已排序結果變成i項已排序序列。
時間複雜度：
最佳情況（完全排序）：只要資料為n筆，則必做n-1次比較。
最差情況（順序相反）：只要資料為n筆，則必做n^2次比較。
空間複雜度：交換時，僅多使用一個空間來儲存暫存值。
穩定排序：數值等於不會進行交換動作。
插入排序演算法
insertion sort algorithm
void insertion_sort(int a[],int n)
{
int i,j;
for (i=1; i<=n-1; i++) j=i; while (j>0) && (a[j]
選擇排序演算法
selection sort algorithm
void selection_sort(int a[],int n)
{
int i,j,min;
for (i=0; i<=n-2; i++) min=i; for (j=i+1; j<=n-1; j++) if a[j]
for (j=0; j
swap(a[j],a[j+1]);
}
Quick Sort（快速排序法）
特性：平均狀況下，執行時間最短的排序法。採用divide and conquer概念。
作法：每回合拿第一筆資料當作C.K.，使用兩個變數，i從第一筆資料開始找筆C.K更大的值，j從第n筆資料開始找比C.K.小的值。當i
時間複雜度：
最佳情況（完全排序）：只要資料為n筆，則必做n+c n*logn次比較。
最差情況（順序相反）：只要資料為n筆，則必做n^2次比較。
空間複雜度：
最佳：O(logn)
最差：O(n)
不穩定排序：不管中間排序狀況，只要條件符合，一蓋交換。會有5+>5情況發生。
快速排序演算法
quick sort algorithm
void quick_sort(int a[],int m,int n)
{
int i,j,k;
if m < i="m;" j="n+1;" k="a[m];">k);
if i <> swap(a[m],a[j]);
quick_sort(a,m,j-1);
quick_sort(a,j+1,n);
}
Merge Sort（合併排序法）
特色：較常使用於外部排序法。
作法：有兩種。
Iterative Merge Sort
兩兩一對，一對對比較後合併。
26,5,77,1,61,11,59,15,48,19
[26,5],[77,1],[61,11],[59,15],[48,19]
[5,26],[1,77],[11,61],[15,59],[19,48]
[1,5,26,77],[11,15,59,61],[19,48]
[1,5,11,15,26,59,61,77],[19,48]
1,5,11,15,19,26,48,59,61,77
Recursive Merge Sort
Divide and Conquer
26,5,77,1,61,11,59,15,48,19
[5,26],77,[1,61],[11,59],15,[19,48]
[5,26,77],[1,61],[11,15,59],[19,48]
[1,5,26,61,77],[11,15,19,48,59]
1,5,11,15,19,26,48,59,61,77
時間複雜度：最佳、最差、平均均相同為O(n*logn)。
空間複雜度：O(n)。
穩定排序法：數值等於不會交換。
Heap Sort（堆積排序法）
關於Heap Tree請看Tree章節相關介紹。
進行Heap Sort之前，請先建立Heap Tree。
從Heap Tree中把Root Output出來，就是排序後的結果了。
可以選擇建立Max-Min Heap Tree或是Min-Max Heap Tree，輸出結果就分別是由大到小或是由小到大。
搜尋與排序向來是資結與演算法的重點！~
沒有留言:
張貼留言