基本介紹
- 中文名：算法列表
- 外文名：List of Algorithm
- 領域：計算機科學
- 含義：各類算法的集合
- 舉例：排序算法列表
- 包含：算法
數據結構,鍊表,棧,佇列,樹,二叉樹,二叉查找樹,字典樹,排序算法,快速排序,合併排序,桶排序,基數排序,
數據結構
鍊表
- 鍊表是一種由節點（Node）組成的線性數據集合，每個節點通過指針指向下一個節點。它是一種由節點組成，並能用於表示序列的數據結構。
- 單鍊表：每個節點僅指向下一個節點，最後一個節點指向空（null）。
- 雙鍊表：每個節點有兩個指針p，n。p指向前一個節點，n指向下一個節點；最後一個節點指向空。
- 循環鍊表：每個節點指向下一個節點，最後一個節點指向第一個節點。
- 時間複雜度：
- 索引：O(n)
- 查找：O(n)
- 插入：O(1)
- 刪除：O(1)
棧
- 棧是一個元素集合，支持兩個基本操作：push用於將元素壓入棧，pop用於刪除棧頂元素。
- 後進先出的數據結構（Last In First Out, LIFO）
- 時間複雜度
- 索引：O(n)
- 查找：O(n)
- 插入：O(1)
- 刪除：O(1)
佇列
- 佇列是一個元素集合，支持兩種基本操作：enqueue 用於添加一個元素到佇列，dequeue 用於刪除佇列中的一個元素。
- 先進先出的數據結構（First In First Out, FIFO）。
- 時間複雜度
- 索引：O(n)
- 查找：O(n)
- 插入：O(1)
- 刪除：O(1)
樹
- 樹是無向、聯通的無環圖。
二叉樹
- 二叉樹是一個樹形數據結構，每個節點最多可以有兩個子節點，稱為左子節點和右子節點。
- 滿二叉樹（Full Tree）：二叉樹中的每個節點有 0 或者 2 個子節點。
- 完美二叉樹（Perfect Binary）：二叉樹中的每個節點有兩個子節點，並且所有的葉子節點的深度是一樣的。
- 完全二叉樹：二叉樹中除最後一層外其他各層的節點數均達到最大值，最後一層的節點都連續集中在最左邊。
二叉查找樹
- 二叉查找樹（BST）是一種二叉樹。其任何節點的值都大於等於左子樹中的值，小於等於右子樹中的值。
- 時間複雜度
- 索引：O(log(n))
- 查找：O(log(n))
- 插入：O(log(n))
- 刪除：O(log(n))
字典樹
- 字典樹，又稱為基數樹或前綴樹，是一種用於存儲鍵值為字元串的動態集合或關聯數組的查找樹。樹中的節點並不直接存儲關聯鍵值，而是該節點在樹中的位置決定了其關聯鍵值。一個節點的所有子節點都有相同的前綴，根節點則是空字元串。
排序算法
快速排序
- 穩定：否
- 時間複雜度
- 最優：O(nlog(n))
- 最差：O(n^2)
- 平均：O(nlog(n))
合併排序
- 合併排序是一種分治算法。這個算法不斷地將一個數組分為兩部分，分別對左子數組和右子數組排序，然後將兩個數組合併為新的有序數組。
- 穩定：是
- 時間複雜度：
- 最優：O(nlog(n))
- 最差：O(nlog(n))
- 平均：O(nlog(n))
桶排序
- 桶排序是一種將元素分到一定數量的桶中的排序算法。每個桶內部採用其他算法排序，或遞歸調用桶排序。
- 時間複雜度
- 最優：Ω(n + k)
- 最差: O(n^2)
- 平均：Θ(n + k)
基數排序
- 基數排序類似於桶排序，將元素分發到一定數目的桶中。不同的是，基數排序在分割元素之後沒有讓每個桶單獨進行排序，而是直接做了合併操作。
- 時間複雜度
- 最優：Ω(nk)
- 最差: O(nk)
- 平均：Θ(nk)
