排序算法之：循环不变式在 Patience Sorting 中的正确性证明

题目描述：
证明 Patience Sorting（耐心排序）算法中循环不变式的正确性。该算法通过将元素依次放入若干堆中，最终利用堆顶性质实现排序。需要严格证明在算法执行的每个阶段，循环不变式如何保证部分有序结构的正确性。

解题过程：

1. 算法概述
   Patience Sorting 分为两个阶段：

• 发牌阶段：将元素依次放入堆中，每个新元素只能放在比它大或相等的堆顶元素上，否则创建新堆
• 收集阶段：反复选取最小堆顶元素构成有序序列

2. 关键数据结构定义
   设 Piles[] 为堆的集合，每个堆是一个栈结构（后进先出）
   定义循环不变式：
   (1) 每个堆内部从上到下严格递减
   (2) 堆顶元素从左到右非严格递增

3. 初始化证明
   初始状态：空数组，0个堆

• 条件(1)：无堆，自然满足
• 条件(2)：无堆顶，自然满足
  循环不变式在初始状态下成立

4. 维护证明（发牌阶段）
   对于新元素 x 的插入：
   情况1：x ≥ 所有堆顶元素
   创建新堆 [x]

• 新堆只有一个元素，满足(1)
• 新堆顶 x ≥ 最右堆顶，满足(2)

情况2：找到最左堆顶 ≥ x 的堆
将 x 压入该堆

• 原堆顶 y ≥ x，压入后新堆顶为 y，保持(2)
• 原堆满足递减，x ≤ y，压入后仍递减，满足(1)

5. 收集阶段正确性
   关键引理：每次取最小堆顶元素时，该元素一定是当前全局最小值
   证明：

• 设最小堆顶为 m，所在堆为 P
• 根据(2)，P 左侧堆顶都 ≤ m
• 根据(1)，P 中下方元素都 < m（严格递减）
• P 右侧堆顶都 ≥ m，其下方元素都 > 对应堆顶（递减性传递）
  因此 m 确实是当前全局最小值

6. 终止条件
   当所有堆为空时：

• 已输出 n 个元素
• 每次输出都是当前最小值
• 最终得到完整有序序列

7. 实例验证
   以 [3,1,4,2] 为例：
   发牌阶段：
   Pile1: [3] → [3,1] → [3,1] [4] → [3,1] [4,2]
   收集阶段：
   最小堆顶1 → 最小堆顶2 → 最小堆顶3 → 最小堆顶4
   输出：[1,2,3,4]

8. 形式化证明
   通过数学归纳法：
   基础：处理0个元素时成立
   归纳：假设处理k个元素时成立，证明处理k+1个时：

• 插入新元素后保持堆性质
• 收集阶段每次能取到最小值
  由归纳法可知对任意n都成立

这个证明确保了 Patience Sorting 在任何输入情况下都能正确排序，同时揭示了其与最长递增子序列的深刻联系。