Please enable JavaScript.
Coggle requires JavaScript to display documents.
資料結構 (排序 (bubble sort 氣泡排序 O(n^2) (毎次兩個兩個排序，會將最大放到最後，重複到排完。), selection…
資料結構
排序
bubble sort 氣泡排序 O(n^2)
毎次兩個兩個排序，會將最大放到最後，重複到排完。
selection sort 選擇排序 O(n^2)
從無序區選擇最小放到有序區的末端，直到排完
insertion sort 插入排序 O(n^2)
從無序區依序插入有序區的正確位置，需要很多交換，會把後面的元素往後挪。
quick sort 快速排序 O(n log n)
隨便選一個數將區間分成大數區跟小數區，再對各別區間遞迴處理。
heap sort 堆排序 O(n log n)
從堆頂把根卸出來放在有序區之前，再取消復原堆。
很像二元搜尋樹。
merge sort 合併排序 O(n log n)
毎兩個相鄰數字排序好成為序列 ，再毎兩個序列merge。
樹
走訪 traversal
後序走訪 postorder traversal 左、右、根
中序走訪 inorder traversal 左、根、右
前序走訪 preorder traversal 根、左、右
合併走訪 merge traversal ?
層序走訪 Level-order Traversal 每層每層
實例
將資料建構成二元搜尋樹，可以中序走訪完成排序
資料建成堆積樹，可找出極值
二元搜尋樹 Binary search tree
所有節點的左子樹都小於該結點，右子樹大於該結點
堆積樹 (Heap tree)
Max Heap tree 所有父節點都大於子節點
Min Heap tree 所有父節點都小於子節點
Data Type
long (4 byte)
single float (4 byte)
int (4 byte)
double (8 byte)
圖
實例
建構網路時，可利用最小成本演算法來決定連通圖
找最短路徑時，以節點表示每一步驟中候選的對象
普林演算法 (Prim's algorithm)
從出發點選擇權重最小的的邊所展開的樹，即最低成本展開樹
戴克斯特拉演算法（Dijkstra's algorithm）
廣度優先搜尋來找出兩節點之間的最短路徑
矩陣
三角矩陣
上三角：對角線左下方為0
下三角：對角線右上方為0
嚴格：連對角線也為0
Bag
像袋子一樣，可以隨意加入或刪除元素，也不在意排序即對應的位置，也不管執行刪除是刪除哪一個元素。
