堆排序

簡單選擇排序的優化
結合了插入排序和歸并排序的優點
原地排序
不穩定

存儲結構：數組
堆的順序表示法：二叉樹的層序遍歷
二叉堆，完全二叉樹
大頂堆：每個節點的值 ≥ 其子節點的值

下標從0開始
父節點：(i-1)/2
左子節點：2i+1
右子節點：2i+2

1. 建堆，簡化/最簡單
   根節點的左右子樹都是堆
   只有根節點不滿足堆

2. 下沉
   將根節點與左右孩子比較
   若不滿足堆
   則交換根與較大的結點
   一直到葉子結點
   或所有子樹均為堆為止

3. 倒數第一層一定是堆
   倒數第二層不一定滿足堆
   從下向上，下沉，建堆

4. 建堆
   從最后一個分支結點（n / 2 - 1）開始建堆
   直到根節點為止
   是 O (n) 而不是 O (n logn)

5. 排序
   根節點和最后一個元素交換（原地排序）
   隊尾減1（排序n-1次）
   根節點的左右子樹都是堆
   只有根節點不滿足堆
   下沉（調整成堆）

6. 上浮
   當前節點與父節點比較
   若不滿足堆
   則交換當前節點與父節點
   一直到堆頂
   或恢復成堆

7. 對比
   上浮
   新元素插入堆尾
   或大根堆中某個元素的值增大
   下沉
   初始建堆
   或堆頂被移除
   或大根堆中某個元素的值減小

1→3，3→4
2→4
2→5

每一趟選擇最大元素
由簡單選擇排序的 O（n）降為 O（logn）

上浮和下沉都是 O (logn)

二路歸并排序（非遞歸，自底向上）

分治法
穩定
緩沖區

1. 兩個有序序列合并成一個有序序列C
   逐一比較
   較小者放入 C
   如果相等，則取靠前的序列（穩定）
   取出較小者的下一個元素再次比較
   直到其中一個序列的元素全部放入 C
   再將另一個序列的元素放在 C 的尾部

2. 一趟歸并排序
   合并相鄰序列
   三種子序列合并情況
   i 為相鄰序列中的第一個元素的下標

   1. i <= n - 2h
      至少還有兩個長度為 h 的序列

   2. i > n - 2h && i < n - h
      只有兩個子序列
      右子序列長度小于 h

   3. i >= n - h
      只有一個子序列

3. 完整的歸并
   兩個數組相互歸并
   每進行一趟歸并排序后
   子序列長度 h 翻倍
   直到子序列長度 h >= 總長度n
   （臨時數組歸并到到原數組時
   h >= n 可以
   但原數組歸并到臨時數組時不行）

logn 趟排序
每趟排序都要劃分成兩半
二叉樹高度 logn取整 + 1

每趟排序 O（n）
每趟排序都要歸并所有元素

二路歸并排序（遞歸，自頂向下）

1. 合并
   參考非遞歸的合并

2. 劃分
   int middle = left + (right - left) /2
   與數組【middle + 1......right】相比
   數組【left......middle】多0到1個元素

3. 排序 r，結果 r1
   r 劃分成左右子列
   分別排序左右子列到 r2（遞歸）
   將 r2 的左右子列 合并 到 r1

4. 遞歸終止
   當區間長度為 1 時
   left == right
   數組本身已有序
   直接將 r[left] 復制到 r1[left]

5. 調用
   待排數組和結果數組都是r
   （結果存回 r）
   （最終排序結果直接覆蓋原始數組r）

棧深 logn
每趟排序都要劃分成兩半

每層的歸并 O (n)
每層都要遍歷所有元素

快速排序（Hoare 分區）

起泡排序的優化（相鄰 → 兩端向中間）
不穩定
遞歸樹

交換較少
隨機數據性能更優
對已排序數組性能較差

1. 基準
   left 作為基準
   分區
   將基準放在左右指針上
   返回基準元素的位置

2. 分區
   左指針初始化：left
   右指針初始化：right
   重復以下操作直至左右指針相等

   • 右指針向左找小于基準的元素
     賦值覆蓋左指針指向的元素
   • 左指針向右找大于基準的元素
     賦值覆蓋右指針指向的元素

3. 遞歸
   參考lomuto分區的遞歸

快速排序（Lomuto 分區）

交換較多
減少有序數組的最壞情況概率

1. 基準
   middle 作為基準
   int middle = left + (left - right) / 2
   分區前 交換 right 與 middle
   分區后 交換 right 與 A 的下一個位置
   返回基準值的索引

2. 分區
   小于等于區域：A
   i 為 A 的最后一個元素的索引
   初始為 left - 1（升序排序）
   遍歷 [ left， right - 1 ]
   若當前元素小于等于基準值
   擴展 A
   交換 A 的最后一個元素 與 當前元素

3. 排序 [ left， right ]
   分區，獲取基準索引 pivot
   排序 [ left， pivot - 1 ]
   排序 [ pivot + 1， right ]

4. 遞歸終止
   當區間長度為 1 時
   left == right 時直接返回

遞歸深度 O(log n)
分區 O(n)

希爾排序

直接插入排序的改進

1. 增量序列

   • 原始序列
     n/2, n/4, ..., 1

   • Hibbard 序列
     2^k - 1

   • Knuth序列
     遞歸：h = 3h + 1
     迭代：(3^k - 1) / 2

   • Sedgewick序列
     9×4^k - 9×2^k + 1
     4^k - 3×2^k + 1
     1, 5, 19, 41, 109, 209, 505……

   • 斐波那契序列

2. 劃分子集
   數組被分為 gap 個獨立的子序列
   子序列的元素索引間隔為 gap
   對每個子序列執行插入排序

3. 插入排序

   1. 法一
      對一個子序列插入排序后
      再對下一個子序列插入排序

   2. 法二
      先依次對每一個子序列的第二個元素插入排序
      再依次對每一個子序列的第三個元素插入排序
      接著是第四個，第五個……

直接插入排序

穩定
適合待排序列基本有序
正序時最好，O(n)，不用移動
逆序時最差

1. 整體思路
   無序區 pop_front
   有序區 upper_bound
   有序區 vector 的 insert 單個元素
   重復以上操作直至無序區為空

2. n - 1 趟循環
   從 r[1] 開始插入
   逐步擴展為 r[n - 1]

3. 邊查找邊后移
   從后向前（穩定）
   順序查找

折半插入排序/折半查找

有序表
判定樹是平衡二叉樹

簡單選擇排序

1. n - 1 趟循環

   • 第 i 趟循環選擇出第 i 小的
     A：已排序區
     B：待排序區

2. 每趟循環的整體思路
   B 找最小值的索引 min
   swap ( B[min]， B.front() )
   B.pop_front()
   A.push_back()

3. 找第 i 小的元素
   設 B 中第一個元素最小
   依次與 B 中的剩余元素比較
   查找 B 中最小的元素的位置

4. 交換無序區最小元素與無序區第一個元素
   當 min != i 時
   r [ min ] 與 r [ i ] 交換
   相當于從 B 中取出最小的元素
   加入 A 中

O（n2）
不穩定

改進的冒泡排序

穩定

1. 改進
   bound：有序區第一個元素
   pos：找本趟排序的 bound
   本趟排序前，將上一趟的 pos 賦值給 bound
   firstpos
   前一趟排序，交換開始位置的前一個位置
   本趟排序，交換開始位置

2. 改進前后對比

   • 改進前：每次都將無序區最大的元素加入有序區
     改進后：每次都將至少一個元素加入有序區
     包含無序區最大的元素

   • bound 防止后部排好的元素重復比較
     firstpos 減少前部的比較次數

   • 改進前：循環 n - 1 次
     改進后：循環 直至本趟排序結束后 pos == 0

3. 相鄰交換（穩定）
   如果 pos == 0，則更新 firstpos
   更新 pos

雙向冒泡排序

計數排序

O(n + k)
穩定

待排序數組A
2，3操作對應 計數數組B
結果數組C

1. min, max
   O (n)

2. 各個數值的個數
   O (n)
   創建大小為 max - min + 1 的 B
   元素大小 x，則 B 的索引 x - min

3. 不大于 x 的個數
   O (k)

4. 反向遍歷
   O (n)
   從后向前遍歷A（保證穩定性）
   A [ i ] 對應 C 的索引 j
   C [ j ] 對應 B 的索引 k
   B [ k ] = A [ i ]
   C [ j ]--

桶排序（ai版本）

O (n + k + nlog(n/k))

1. min, max
   O (n)

2. 桶數
   如果元素數量 <= 100，桶數量 = 元素數量
   如果元素數量 ＞ 100，桶數量 = 元素數量開平方

3. 每個桶的范圍
   range = (max - min) / bucketCount

4. 創建桶
   vector<vector<T>> 類型

5. 分配
   O (n)
   元素大小 x，則桶索引 (x - min) / range
   若為最大值，桶索引要減一

6. 桶內排序
   O (n log(n/k))
   決定了是否穩定

7. 遍歷，覆蓋
   O (n + k）
   遍歷桶，如果桶不空
   將元素覆蓋在原數組

桶排序（課本版本）

O (n + k)
適合整數，連續
穩定

1. min, max
   O (n)

2. 桶數
   最大值 - 最小值 + 1

3. 創建桶
   vector<list<T>> 類型

4. 分配
   O (n)
   元素大小 x，則桶索引 x - min
   插入桶的尾部（保證穩定）

5. 遍歷，拼接
   O (k)
   從前向后遍歷桶，如果桶不空
   將其 splice 到 result 的末尾

   • 從后向前遍歷桶，如果桶不空
     將其 splice 到 result 的頭部 也行

   • result 是 list<T> 類型

基數排序（LSD）

O(d*(n + k))
k 一般是 10
穩定

1. 找最大值 和 最小值

   • 如果事先能確定一定是非負數
     則不需要找最小值

2. 最大位數

3. 從最低位到最高位
   逐位進行 計數排序

   1. 不需要找最值

   2. B 的大小為 10

   3. 第 d 位為 x ，則 B 的索引 x

各種排序的比較和選擇

簡單排序

1. 分治：冒泡，直接插入，簡單選擇
   分為已排序區和待排序區

2. 原地排序：冒泡，直接插入，簡單選擇

3. 基本有序：直接插入，O(n)時間

4. 大型對象：簡單選擇，O(n)次移動

復雜排序

1. 快
   快速排序（非基本有序）

2. 原地
   堆排序
   希爾排序
   歸并排序（鏈表）

3. 穩定
   歸并排序

4. 最大/最小的 n 個數
   堆排序

5. 合并兩個有序數組
   歸并排序

非比較排序

1. 都是非原地排序

2. 都要找最值

3. 分布均勻
   桶排序（ai 版本）

4. 小數
   桶排序（ai 版本）
   基數排序

   • 只適合小數位數固定
     要轉換成整數再排序
     不如桶排序

5. 負數
   計數排序
   桶排序
   基數排序

   • 正負分離 + 負數子數組反轉

6. 極差較小
   計數排序

7. 極差較大
   基數排序

8. 最大/最小的 n 個數
   桶排序
   計數排序（稍作修改）

9. 尾部的 n 個數的排名
   計數排序

10. 某個元素的個數
    計數排序

Floyd

多源
任意兩個頂點間的最短路徑

dijkstra

無負權
有向圖
單源
求一點到各點的最短路徑和長度

性質

1. 子路徑最優性（最優子結構）
   最短路徑上任意兩點之間的路徑都最短

2. 最優子結構體現為
   從源點到某個頂點的最短路徑
   一定包含路徑上其他頂點到源點的最短路徑

3. prev數組
   以源點為根的最短路徑樹

4. Q 為已確定最短路徑的頂點集合
   迭代中，頂點 a 暫未加入 Q
   則 dist[a] 滿足：

   • 該路徑僅由兩部分組成
     源點到 Q 中某頂點 u 的最短路徑（已確定）
     邊（u，a）

   • 在當前集合 Q 下
     源點到 a 的最短可能路徑

5. 每次確定的頂點 u 的距離 d[u]
   一定是最短路徑長度

   • 若存在更短路徑
     該路徑必然經過某個未確定的頂點 v
     但 v 的距離 d[v] 至少為 d[u]
     （否則 v 會在 u 之前被選擇），
     而無負權邊無法讓路徑變短，故矛盾

6. 按照頂點到源點的最短路徑長度
   從小到大的順序，
   依次確定頂點

算法流程

1. 初始
   鄰接矩陣
   頂點數n
   源點s：dist[s] = 0
   其他頂點v：dist[v] = MAX
   （表示不可達）
   數組 visited 初始均為 false

2. 迭代
   重復以下操作 n 次
   （每次確定 1 個頂點
   總共 n 個頂點）

   • 選頂點
     從所有未標記的頂點中
     選擇 dist[v] 最小的頂點 u
     此時 u 的最短路徑已確定

   • 更新距離
     遍歷 u 的所有鄰接頂點 v
     若通過 u 到 v 的距離小于 dist[v]
     則更新 dist[v]

3. 長度
   數組 dist： 源點到各頂點的最短路徑長度

   • 長度為0：源點到源點，跳過
   • 長度為MAX：不可達
   • 長度∈(0, MAX)：源點到可達頂點

4. 路徑

Kruskal

無向圖
最小生成樹

• 包含所有頂點
  頂點數 - 1 條邊
  權重之和最小

離散數學知識

1. 等價關系
   自反，對稱，傳遞
   集合S上的二元關系R

2. 等價類
   兩個等價類要么相等
   要么沒有交集
   所有等價類的并集為集合S

3. 商集S/R
   等價類的集合
   集合的集合
   集合S的一個劃分

4. 規范映射/投影映射
   π: S→S/R, π(x)=[x]

數學與編程

1. 一個連通分量：一個等價類

2. 并查集初始化：
   每個元素獨立成一個集合：每個元素都是一個等價類
   每個元素的根節點是自己：自反性

3. find函數：
   根節點：等價類代表元素
   返回根節點：規范映射
   路徑壓縮：傳遞性

4. unite函數：
   根是否相同：是否在同一個等價類
   合并集合：合并等價類

算法流程

1. 初始化
   邊的數量
   頂點數量
   三元組表（頂點1，頂點2，權重）
   初始化并查集數組

2. 排序
   edge結構體，重載比較運算符
   所有邊按權重從小到大排序

3. find函數（迭代）

4. find函數（遞歸）

   • 查找結點 a 的根節點
   • 如果結點 a 不是根節點
     • 遞歸查找其父節點的根節點
     • 路徑壓縮
       • 結點 a 的父節點變成根節點
       • 后續查詢效率接近 O (1)
   • 如果結點 a 是根節點
     • 遞歸終止
     • 直接返回 a

5. unite函數

   • 查找 a 和 b 的根節點 ra 和 rb
   • 若根節點相同
     • 則兩集合合并失敗
   • 若根節點不同
     • 將 ra 的父節點設為 rb
       • 反過來也行
       • 并查集：通過樹結構表示集合
     • 則兩集合合并成功

6. 遍歷邊
   若添加的邊不會形成環
   則依次添加邊到生成樹中，
   直到添加 n-1 條邊
   或所有邊處理完畢

判斷是否成環

1. 并查集
   每個集合由一棵樹表示
   無向圖，若兩個節點屬于同一集合
   則添加連接它們的邊會形成環

判斷圖是否連通

1. 是否為n - 1 條邊

2. 并查集
   任選一個節點的根作為基準
   判斷剩下的結點的根是否與基準相同
   若不相同，則圖不連通

3. 任選一個節點作為起點
   BFS 或 DFS 遍歷所有可達節點
   若訪問的節點數等于總節點數
   則圖連通；否則不連通。

時間復雜度由排序決定
O (ElogE)，E 是邊的數量

Kruskal與其他算法

1. find函數（迭代）
   • 找到根節點

     int root = x;
     while (parent[root] != root) {
       root = parent[root];
     }
     

   • 將路徑上所有節點的父節點直接設為根
     • 保存當前節點的父節點
       將當前節點的父節點設為根
       處理原父節點

1. dijkstra的路徑

   int pre = i;
   string path = G.name[pre];
   while (Path[pre] != -1) {
       pre = Path[pre];
       path = G.name[pre] + "->" + path;
   }
   cout << path << endl;
   

Kahn，CPM

有向圖

數學知識補充

1. 拓撲序列：
   對于有向邊 u → v
   u 在排序結果中一定位于 v 之前

2. 有向圖存在拓撲序列，
   ←→圖是有向無環圖

算法流程

1. 初始化

• 節點數
• 邊數
• 鄰接表
  • 任務開始的交接點編號小者優先
    起點編號相同時
    與輸入時任務的順序相反
  • 鄰接表保持邊的插入順序
    逆序遍歷即可
  • 鄰接矩陣不存儲邊插入順序
    需額外記錄邊順序
• 入度數組
• 最早發生時間ve
• 最晚發生時間vl
• 輸入邊（頂點1，頂點2，權重）
• 計算所有頂點的入度
  • 輸入一條邊
    頂點2的入度 +1

1. 拓撲排序
   所有入度為 0 的頂點入隊
   每次從隊列中取出一個頂點
   加入拓撲序列
   鄰接頂點的入度減 1
   若鄰接頂點入度變為 0，入隊
   若拓撲序列的頂點數等于圖的總頂點數，則無環
   否則存在環

   • 未被排序的頂點形成環

2. 最早發生時間ve
   初始化ve數組全為0
   ve[j] = 所有前驅節點中 max(ve[i] + weight(i→j))

   • 翻譯成代碼
     遍歷 i 的所有后繼節點
     對于某一個后繼節點 j
     ve[j] = max(ve[j], ve[i] + weight(i→j))

   • 思想類似于
     稀疏矩陣的乘法
     向量的加法和數乘

3. 最晚發生時間vl
   初始化vl數組為工程總時間T
   （所有ve的最大值）
   vl[i] = 所有后繼節點中 min(vl[j] - weight(i→j))

   • 翻譯成代碼
     遍歷 i 的所有后繼節點
     對于某一個后繼節點 j
     vl[i] = min(vl[i], vl[j] - weight(i→j))

4. 計算方向
   ve：拓撲正序
   vl：拓撲逆序

   • 要計算節點i的vl
     必須先知道所有后繼節點j的vl值
     拓撲逆序保證在計算節點i時
     其所有后繼節點都已計算完成

   • ve數組的計算
     拓撲排序
     可以放在一起/同時進行

5. 關鍵活動
   判定：對每條邊(i→j)：
   ve[i] == vl[j] - weight

   • 活動a：邊（i→j）
     最早開始時間 e (a) = ve[i]
     最遲開始時間 l (a) = vl[j] - weight(i→j)

   • 關鍵活動：e(a) = l(a)
     活動 a 沒有緩沖時間
     必須按時完成
     否則會延誤整個項目

kahn：
有向圖拓撲序列
有向無環圖DAG

• 并查集：無向無環圖

dfs

bfs

單向靜態鏈表

1. • 將節點歸還至空閑區

     nodes[nodeIndex].next = freeList;
     freeList = nodeIndex;
     

   • 頭插法

     nodes[newNode].next = head;
     head = newNode;
     

2. • 從空閑區獲取節點

     int newNode = freeList;
     freeList = nodes[freeList].next;
     return newNode;
     

   • 刪除

     int temp = head;
     head = nodes[head].next;
     releaseNode(temp);