排序算法之：耐心排序（Patience Sorting） 题目描述 给定一个整数数组，使用耐心排序算法对其进行升序排序。耐心排序的核心思想是将数组元素依次分发到若干"堆"（pile）中，每个堆是一个单调递减的序列，最终通过合并这些堆得到有序结果。该算法名称源自纸牌游戏"耐心"（Solitaire），其时间复杂度为O(n log n)，空间复杂度为O(n)。 解题步骤 创建堆的集合 初始化一个空列表 piles ，用于存放所有堆。每个堆本身是一个列表，且堆顶元素（最后一个元素）是堆中的最小值。 遍历数组中的每个元素 x ： 在 piles 中查找第一个堆顶元素 大于等于 x 的堆（若不存在则新建一个堆）。 将 x 放入该堆顶部（即追加到堆的末尾）。此操作保证每个堆内部是单调递减的。 示例演示 以数组 [7, 2, 8, 1, 3, 4] 为例： 处理 7 ：无现有堆，新建堆 [7] ， piles = [[7]] 。 处理 2 ：堆 [7] 的堆顶7 > 2，放入该堆→ [7, 2] ， piles = [[7, 2]] 。 处理 8 ：现有堆顶2 < 8，新建堆 [8] ， piles = [[7, 2], [8]] 。 处理 1 ：堆顶2 > 1，选择第一个堆→ [7, 2, 1] ， piles 不变。 处理 3 ：堆顶1 < 3，但第二个堆顶8 > 3，放入第二个堆→ [8, 3] ， piles = [[7, 2, 1], [8, 3]] 。 处理 4 ：堆顶1 < 3 < 4，无堆可放，新建堆 [4] ， piles = [[7, 2, 1], [8, 3], [4]] 。 合并堆生成有序数组 由于每个堆顶是堆的最小值，所有堆顶构成一个 最小候选集合 。 反复从所有堆顶中选出最小值，追加到结果数组，并从对应堆中移除该元素（若堆空则移除堆）。 上例中： 堆顶为1、3、4，选最小值1→结果 [1] ，更新堆为 [[7, 2], [8, 3], [4]] 。 堆顶为2、3、4，选2→结果 [1, 2] ，堆变为 [[7], [8, 3], [4]] 。 重复直至所有堆空，最终得到有序数组 [1, 2, 3, 4, 7, 8] 。 算法优化 堆的查找可使用 二分搜索 （因 piles 的堆顶从左到右递增），使建堆步骤优化至O(n log n)。 合并步骤可用 最小堆（优先队列） 维护堆顶，每次取最小值后更新队列。 关键点 耐心排序实质是模拟插入过程，堆的数量等于最长递增子序列（LIS）的长度。 该算法不仅用于排序，还可解决LIS问题（堆的数量即为LIS长度）。