什么是C语言的哨兵？我正在学习Merge排序,并且在合并步骤中遇到使用sentinel作为无限

Question

我正在学习Merge排序,并且在合并步骤中遇到使用sentinel作为无限.

这是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来标记列表的结尾.

在这种特定情况下,当列表的两半被合并回来时,使用无穷大简化了比较逻辑(例如,当合并任何与无穷大相比的东西将会更少时,因此简化了合并结束的处理).