algorithm - C语言中的哨兵是什么？我正在学习合并排序并在合并步骤中使用哨兵作为无穷大

Question

我在学习合并排序时发现在合并步骤中使用哨兵作为无穷大。

这是 Cormen 书中的算法。为什么我们在第 8 步和第 9 步中使用了无穷大？？？

MERGE(A, p, q, r)

1 n1 ← q − p + 1

2 n2 ← r − q

3 create arrays L[1 . . n1 + 1] and R[1 . . n2 + 1]

4 for i ← 1 to n1

5 do L[i ] ← A[ p + i − 1]

6 for j ← 1 to n2

7 do R[ j ] ← A[q + j ]

8 L[n1 + 1] ← ∞

9 R[n2 + 1] ← ∞

10 i ← 1

11 j ← 1

12 for k ← p to r

13 do if L[i ] ≤ R[ j ]

14 then A[k] ← L[i ]

15 i ← i + 1

16 else A[k] ← R[ j ]

17 j ← j + 1

Answer 1

标记是一个虚拟值，用于区分应该存在的值(例如用户输入)和控制值(需要特殊处理的值)。一个简单的例子是使用 null to null 来标记列表的结尾。

在这种特定情况下，无穷大的使用简化了将列表的两半重新合并在一起时的比较逻辑(例如，当合并任何与无穷大相比的东西时，无穷大的数量会更少，因此处理合并被简化了)。