C++ 耐心排序

排序算法是计算机科学的基础，因为它们是许多应用程序和系统的基础。然而，最有效的排序技术之一是耐心排序，因为它基于名为 Patience 或 Solitaire 的纸牌游戏，策略非常巧妙。耐心排序不像快速排序或归并排序那样受欢迎，但其效率接近，时间复杂度为O(nlogn)。

该算法之所以被称为耐心排序，是因为它借鉴了 Patience 纸牌游戏，在该游戏中，我们需要将一副牌按多堆排序。这种排序方法非常有趣，因为它模仿了实际的游戏动作，这些动作是基于牌的排序，而且孩子们喜欢学习。尽管耐心排序是一个理论概念，并未用于实际排序数据，但其简单的方法以及解决相关问题的能力（例如寻找最长递增子序列的长度）使其成为程序员工具箱中的一个附加工具。

在这篇博文中，我们将剖析耐心排序的核心思想及其工作流程。我们还将介绍如何在 C++ 中使用耐心排序，并概述如何在实践中应用它；我们还将重点介绍其时间和空间复杂度。在本文的最后，读者将掌握关于耐心排序如何工作及其使用可能性的充分信息。

理解概念

本质上，耐心排序是一种算法，它模仿了 Patience 纸牌游戏的过程，在该游戏中，牌被分成堆。主要思想是生成多个堆，使得每个堆中的元素从上到下都是递增的。排序通过根据一组定义的标准将输入数组的每个元素归入其中一个堆中，然后合并这些堆来得到排序后的数组来实现。

堆的创建

耐心排序的第一个过程是将对象分成堆。数组中的每个成员都被放入一个堆中，其方式是确保所有堆都包含递增顺序的元素。将元素放入堆的规则如下：

• 找到第一个堆，该堆的顶部元素（牌）不小于当前元素。
• 将此堆与上面的元素一起堆叠。
• 如果没有这样的堆，则使用当前元素创建一个新堆，该堆最初只包含当前元素。
• 通过应用二分查找，我们将能够快速找到每个元素的正确堆。二分查找有助于我们轻松找到应该用于放置元素的堆，从而使算法的效率达到O(nlogn)时间。

合并堆

在所有元素都已排序并放入堆之后，下一步是合并所有这些堆以形成排序后的数组。合并技术包括遍历堆栈，并在每一步中，从每个堆的顶部选择最小的元素并将其放入排序后的数组中。这可以使用最小堆（优先队列）来完成，并且需要 O(m) 的时间。

最小堆使我们能够以最短的时间找到并提取堆顶的最小元素。每次从堆中取出最小的元素时，都会将同一堆中的下一个元素插入到该位置。此过程一直持续到所有堆都变空，并且排序后的数组已用递增顺序的元素形成。

耐心排序的分步算法

耐心排序是一种基于 Patience 纸牌游戏的有趣算法。该算法通过创建和合并 n 个元素堆来工作，并且排序数组通常保持有效，具有O(n log n)的时间复杂度。这是对已分析的分步算法的清晰详细的理论描述。

步骤 1：初始化

当算法开始时，它将堆列表初始化为一个空列表。每个堆最终将包含从堆顶部到底部按递增顺序排列的元素。此时，没有可供处理的元素，因此也没有要组织的堆。

步骤 2：创建堆

算法的主要步骤在一个主循环中进行，在此期间，输入数组的每个元素都必须放置到正确的堆中。此过程的详细操作如下：

遍历元素

如果要遍历输入数组中的所有元素，则遍历过程如下：

查找正确的堆

对于每个元素，查找最左边的堆，该堆的顶部元素（牌）大于或等于当前元素。这有助于保持每个堆的顺序，使得堆按升序排序。

• 为了轻松找到此堆，请应用二分查找。二分查找有助于在 logbase n 的时间复杂度内找到正确的堆，从而将此步骤从 O(n) 减至 O(log n)。
• 如果存在这样的堆，则在该堆的顶部添加元素。如果查看列表并且找不到合适的堆，则当前元素可以添加到 immaculate 堆中。

放置元素

• 将当前元素堆叠到确定的堆上，或者如果当前堆不存在，则开始构建一个新堆。这种放置可确保堆以在放置过程中指示的顺序保持排序。
• 对元素进行排序并将其放入堆中至关重要，因为在合并之后，这些堆的大小应该代表所做的比较次数，并且排序的每个后续步骤都依赖于前一个步骤，因此很容易根据先前步骤的结果来预测其结果。
• 自然，通过对整个数组使用二分查找，此步骤的整体复杂度也为 O(nlogn)。

步骤 3：合并堆

• 在将所有元素放置到堆中后，下一步进行进一步分析是合并这些堆到一个排序列表中。此合并过程使用最小堆（优先队列）来从堆的顶部元素中提取最小的项。合并过程的详细操作如下：

插入初始元素

• 首先，有必要构建一个最小堆，这是一个由包含数字和堆索引引用的对组成的堆。最小堆的使用使得从所有堆的堆顶提取最小数字成为可能。
• 每个堆的顶部元素应放入最小堆中。除了元素数字之外，还保存每个元素的堆索引，以指示它属于哪个堆。
• 因此，假设有 k 个堆，则堆最初将包含 k 个元素。

提取和替换

以同样的方式，如果堆中还有另一个元素属于该特定堆，则将提取的元素替换为下一个元素。这可以保持堆的大小不变，并确保每个元素都会在某个时候被纳入该过程。

继续进行此提取和替换过程，直到从堆中获得最后一个项目。每次提取和替换操作都确保堆的最小元素始终位于堆的顶部，以便正确排序。

• 从最小堆中弹出第一个元素并返回。保证这个元素是所有当前堆顶中最小的。
• 将此提取的元素放入排序后的数组中。
• 最小堆上的操作，即插入和提取，需要 O(Log n) 的时间。
• O(logk)，其中 k 通常是堆的数量。由于插入和提取操作，每个元素只被插入和提取一次。因此，合并步骤为 O(log)。

步骤 4：结果

在所有合并完成后，来自堆的元素将合并到数组中并按升序排序。该算法保证程序的输出与函数调用相比是已排序的元素。

代码实现

输出

 
Enter the number of elements: 8 
Enter the elements: 6 3 8 1 5 2 7 4 
Original array: 6 3 8 1 5 2 7 4  
Sorted array: 1 2 3 4 5 6 7 8    

耐心排序的优点

• 直观的概念：耐心排序类似于纸牌游戏，因此用户在可视化这项任务时应该不会遇到任何困难。这使得新用户能够相当容易地理解这个过程，特别是关于排序过程。
• 最佳时间复杂度：该算法的时间等于 O(n log n)，这是使用比较的最佳复杂度。由于处理数据集中元素所需的时间减少，因此对于大型数据集来说，它非常高效。
• 在最长递增子序列中的应用：在最长递增子序列中的应用：耐心排序在寻找序列的最长递增子序列时非常有用。这种应用在许多领域都有用，包括但不限于生物信息学和数据分析。
• 稳定性排序：该算法是稳定的，因此可以保留与零等价的元素的相对排列。当相同元素的顺序很重要时，此属性会变得有用。
• 易于实现：令人惊讶的是，使用耐心排序非常精确，并且由两个基本步骤组成 - 二分查找和最小堆。这一事实使得在开发阶段用编程语言编写和调试代码相当容易。

耐心排序的缺点

• 不常用：然而，尽管耐心排序具有理论上的美感，但在实践中并不常用。其他算法，例如快速排序或归并排序，更常使用，仅仅是因为它们已知的性能以及在哪里可以找到支持它们的库。
• 较高的空间复杂度：堆和优先队列需要额外的空间，将算法的空间复杂度提高到 O(n)。这可能是一个缺点，尤其是在执行设备内存有限的环境中。
• 二分查找和堆的开销：最后值得提及的关于这个结论的特点是，二分查找和最小堆都会增加时间复杂度，并在一定程度上增加算法的复杂性，在简单的情况下，可以通过采用更简单的排序算法来解决。
• 通用性较差：与许多其他排序算法相比，耐心排序稍微更密集且通用性较差。该算法专门设计用于查找子序列，而不是通用的排序解决方案。