Quick Sort
做法 Quick Sort 與 Merge Sort 雖然利用同樣的概念，但是作法上差異很大，它會先從陣列中選擇一個「樞紐」（pivot），然後將所有小於樞紐的值都移到它的左邊、將所有大於樞紐的值都移到它的右邊。移動的過程我們並沒有去做排序，我們只是先將它們移到某一邊。ps. 結束時，只有 pivot 會在它最後正確的位置上（也就是只有樞紐是在排好序的位置）。 當樞紐完成以後，我們對左半部分再次進行同樣的處理（找到 pivot、移動位置），再處理右半部分。 時間複雜度分析： 最壞情況(Worst Case): O(n²) 當基準值總是選到最大或最小元素時 當數組已經排序或逆序時 分割非常不平衡時 最好情況(Best Case): O(n log n) 當每次分割都能將數組平均分成兩半時 遞迴樹的深度為 log n 每層需要 O(n) 的操作 平均情況(Average Case): O(n log n) 在隨機數據下，通常能達到這個效率 這也是實際應用中最常見的情況 1234567891011121314151617181920212223242526272829...
Insertion Sort
演算法原理： 將數組分為已排序和未排序兩部分 從未排序部分取出一個元素 在已排序部分找到適當的位置插入 重複步驟2-3，直到所有元素都排序完成 時間複雜度分析： 最壞情況(Worst Case): O(n²) 當數組完全逆序時 每個元素都需要移到最前面 比較和移動次數最多 最好情況(Best Case): O(n) 當數組已經排序時 每個元素只需要比較一次 不需要移動元素 平均情況(Average Case): O(n²) 對於隨機排列的數組 平均需要移動和比較 n²/4 次 空間複雜度： O(1)，只需要一個臨時變量存儲 key 123456789101112131415161718192021222324static void InsertionSort(int[] arr){ int n = arr.Length; // 從第二個元素開始，因為第一個元素可以視為已排序 for (int i = 1; i < n; i++) { // 保存當前要插入的元素 int ...
Selection Sort
演算法原理： 將數組分為已排序區域和未排序區域 在未排序區域中找到最小元素 將找到的最小元素與未排序區域的第一個元素交換 重複步驟2-3，直到所有元素都排序完成 時間複雜度分析： 最壞情況(Worst Case): O(n²) 外層循環執行 n-1 次 內層循環第一次執行 n-1 次，第二次 n-2 次，依此類推 比較次數：(n-1) + (n-2) + … + 1 = n(n-1)/2 交換次數：最多 n-1 次 最好情況(Best Case): O(n²) 即使數組已經排序 仍然需要執行所有的比較操作 只是交換次數可能減少 平均情況(Average Case): O(n²) 與最壞情況相同 選擇排序的特點是比較次數固定 空間複雜度： O(1)，只需要一個臨時變量來進行交換 選擇排序的特點： 優點： 實現簡單 交換次數少（最多 n-1 次） 對於小規模數據較為高效 缺點： 時間複雜度固定為 O(n²) 對於大規模數據效率低 不穩定排序（相同值的相對順序可能改變）
Bubble Sort
由後而前依序將兩兩相鄰的值互相比較，直到所有的值都被排到正確的位置為止。 最壞情況 (Worst Case): O(n²) 當數組完全逆序時（如 [5,4,3,2,1]） 外層循環需要執行 n-1 次 內層循環每次需要執行 n-i-1 次 總比較次數：(n-1) + (n-2) + … + 1 = n(n-1)/2 所以是 O(n²) 最好情況 (Best Case): O(n) 當數組已經排好序時（如 [1,2,3,4,5]） 只需要執行一次外層循環 內層循環執行 n-1 次比較 由於沒有發生交換，會提前退出 所以是 O(n) 平均情況 (Average Case): O(n²) 在隨機數據的情況下 仍然需要進行大量的比較和交換 複雜度接近最壞情況 圖示現假設有一陣列 [6,5,4,9,1]，要透過氣泡排序將陣列由小排到大的過程如下： 1234567891011121314151617181920212223242526272829static void BubbleSort(int[] arr){ int n = arr....
Binary Search Tree
定義: 若一顆二元樹滿足以下兩點:a. 左子節點的值小於節點的值 b. 右子節點的值大於節點的值 即可稱為二元搜尋樹 12345 2 6 / \ / \1 3 5 8 <-----像這樣, 這兩棵都是BST / / \ 3 7 9 二元搜尋樹的查詢, 插入, 走訪, 查詢最大最小值和刪除操作 提示: 刪除節點有兩個子節點的時候, 要用它的中序後繼來代替該節點, 演算法為: 找到被刪除節點的右子節點, 然後查詢此右子節點下的最後一個左子節點, 即此顆子樹的最小值節點, 這就是被刪除節點的中序後繼節點. 何謂前序, 中序, 後序? 以上圖右邊的三層樹為例, 看1~2層的子樹: preorder 前序: 6 -> 5 -> 8 inorder 中序: 5 -> 6 -> 8 postorder 後序: 5 -> 8 -> 6 若看整顆: 中序: 3 -> 5 -> 6 -> 7 -> 8 -&g...
B-Tree
B-tree是一種高效的資料結構，特別適用於處理大量資料和優化I/O操作。它常用於多存儲系統中，特別是磁盤存儲和數據庫系統，以確保高效的數據組織和查詢。 磁碟存取資料: 磁碟存取資料的基本過程 根據磁柱號碼使磁頭移動到所需要的柱面上, 這一個過程被稱為定位或是查找 根據磁盤面號來確定指定盤面上的磁道 盤面確定以後, 盤面開始旋轉, 將指定磁區的磁軌段移動至磁頭下 磁碟讀取資料是以block為基本單位的, 因此儘量將相關資訊存放在同一個磁區, 同一磁軌中, 以便在讀寫資料時儘量減少磁頭來回移動的次數, 避免過多的查找時間. 當大量的資料儲存在磁碟中時, 如何高效地查詢磁碟中的資料, 就需要一種合理高效的資料結構了 使用時機 檔案系統或著是資料庫為了增加搜尋的效率, 就可以採用此資料結構. 在資料量變大時, 若用線性搜尋檔案中的紀錄, 效率其實是不好的, 所以這時候就可以建立索引(index), 但資料量又再度增加時, index檔案也會變得很龐大. 為此, 需要一個有效率的搜尋索引, 才能有效率的找到結果. B-Tree 特性 對於一顆m階（階指的是子節點的最大...
Permutation
Permutation to IndexN 筆資料的所有排列一共 N! 種。 一個階乘進位數字，可以代表一個排列。 Lehmer code 又稱 Cantor expansion ：右方數字個數，階乘，作為數量級。右方較小的、尚未出現的數字個數，作為位數。 1234567891011121314151617181920212223const int N = 5; // 定義陣列長度為 5int a[N] = {4, 1, 5, 2, 3}; // 輸入的排列int c[N+1]; // 樹狀數組，用於計算比當前數字小的數字個數int permutation_to_index() { int fac = 1; // 階乘值，用於計算康托展開 int n = 0; // 最終的索引結果 for (int i=1; i<=N; ++i) { // 計算比...
Heap
Binary Heap 為甚麼Binary heap 有兩個特點： Binary heap 是一個完全二元樹 (complete binary tree)，完全樹的意思是除了最後一層外每一層都填滿，最後一層必須由左至右填入。 Max heap 的每個結點的值，大於其左節點的值和右節點的值，根節點是整棵樹最大的節點；Min heap 每個結點的值，小於其左節點的值和右節點的值，根節點是整棵樹最小的節點。
SOLID
Abstract V.S. Virtual Abstract: An abstract class/method MUST be implemented by derived classes Abstract classes cannot be instantiated directly Classes with abstract methods must be declared abstract Abstract methods have no implementation in the base class Virtual: A virtual method CAN be overridden by derived classes Virtual methods have a default implementation in the base class Classes with virtual methods can be instantiated Derived classes may choose to override or use the bas...
關聯式資料庫事務特性
ACID，是指資料庫管理系統（DBMS）在寫入或更新資料的過程中，為保證事務（transaction）是正確可靠的，所必須具備的四個特性：原子性（atomicity，或稱不可分割性）、一致性（consistency）、隔離性（isolation，又稱獨立性，主要針對事務）、持久性（durability）。 在資料庫系統中，一個事務是指：由一系列資料庫操作組成的一個完整的邏輯過程。例如銀行轉帳，從原帳戶扣除金額，以及向目標帳戶添加金額，這兩個資料庫操作的總和，構成一個完整的邏輯過程，不可拆分。這個過程被稱為一個事務，具有 ACID 特性。 資料來源:維基百科 - ACID 四大特性 原子性（Atomicity）：一個事務中的所有操作，需要全部完成，亦或者全部不完成，不會結束在中間某個環節。transaction 在執行過程中發生錯誤，會被 Rollback 到 transaction 開始前的狀態，就像這個事務從來沒有執行過一樣。即，transaction 不可分割、不可約簡。 一致性（Consistency）：在事務開始之前和事務結束以後，資料庫的完整性沒有被破壞。代表寫入的資...
