C++ 合并排序算法

合并排序（Merge Sort）是一种基础的排序算法，属于分治算法家族。它以其效率和可靠性而闻名，并常常被用作衡量其他排序算法的基准。合并排序的核心在于它能够高效地对元素数组或列表进行排序，使其成为计算机科学、数据科学以及数据处理是基础任务的各种其他领域的重要工具。

排序算法简史

排序是计算机科学中的一项基本操作，排序算法的发展有着悠久的历史，可以追溯到早期计算的时代。随着硬件、算法的进步以及对高效数据处理的需求，排序算法不断发展。本历史概述将深入探讨排序算法发展史上的关键里程碑和进展。

20 世纪 40 年代和 50 年代：早期起源

最早的排序算法都很简单，并且依赖于基本操作。其中第一个算法是冒泡排序，它涉及到比较和交换相邻的元素。像 ENIAC 和 UNIVAC 这样的早期计算机使用冒泡排序和其他类似的方法对数据进行排序。这些算法效率不高，时间复杂度为 O(n^2)。

20 世纪 50 年代和 60 年代：算法优化

随着计算机变得越来越强大，对更高效排序算法的需求也变得日益明显。在 20 世纪 50 年代，美国数学家兼计算机科学家约翰·莫奇利（John Mauchly）提出了合并排序的概念。合并排序是一种分治算法，它将数据分成更小的部分，对它们进行排序，然后将它们合并在一起。它提供了更好的性能，时间复杂度为 O(n log n)，是排序领域的重要一步。

20 世纪 60 年代和 70 年代：快速排序和堆排序

在 20 世纪 60 年代初，英国计算机科学家托尼·霍尔（Tony Hoare）提出了快速排序，这是另一种分治排序算法。快速排序因其速度和效率而广受欢迎，在实际应用中通常优于合并排序。但是，它的最坏情况时间复杂度为 O(n^2)，这促使人们进一步研究优化枢轴选择。

大约在同一时间，堆排序被开发出来。该算法基于二叉堆的概念，二叉堆是一种允许高效检索最大（或最小）元素的数据结构。堆排序提供了一种替代排序方法，时间复杂度为 O(n log n)，并且在大型数据集上表现良好。

20 世纪 70 年代和 80 年代：基数排序和混合算法

在 20 世纪 70 年代，基数排序作为一种非比较排序算法而受到关注，它一次处理一位数据。它对于对具有固定长度键的整数或字符串进行排序尤其有效。基数排序在许多情况下提供了线性时间复杂度，并在各种数据处理任务中得到了应用。

20 世纪 80 年代出现了混合排序算法，它们结合了不同排序方法的优点。IntroSort 就是这样一种混合算法，它使用快速排序直到达到一定的递归深度，然后切换到堆排序。这避免了快速排序的最坏情况，并结合了这两种算法的效率。

20 世纪末：现代排序算法的引入

在 20 世纪末和 21 世纪初，Timsort 和 Introspective Sort 等排序算法被开发出来。Timsort 被 Python 和 Java 使用，它结合了合并排序和插入排序，以高效地处理实际数据。Introspective Sort 是快速排序的一个变体，它使用插入排序来提高在小型数组上的性能。

最新进展：并行排序和外部排序

硬件的最新进展以及处理海量数据的需求促使了并行排序和外部排序的研究。并行排序算法利用多核处理器和分布式计算来更快地对数据进行排序。外部排序算法通过利用硬盘或 SSD 等外部存储来管理大规模排序任务，来处理无法完全装入内存的数据。

总之，排序算法的历史证明了计算机科学的演变及其与硬件功能和实际数据处理需求的相互作用。从冒泡排序的卑微开端到如今高效且专业的排序算法，这段旅程反映了在计算中最基本的操作之一：排序，不断追求提高效率。排序算法仍然是研究和创新的主题，确保数据在一个不断扩展的数字世界中能够被有效地组织和处理。

合并排序算法的起源可以追溯到计算机科学的早期以及用于排序数据的算法的开发。约翰·冯·诺依曼（John von Neumann），一位著名的数学家和计算机科学家，常常被认为是 20 世纪 40 年代中期提出了合并和排序的概念。合并排序建立在分治原则的基础上，该原则由约翰·冯·诺依曼正式确立，为它发展成一种高效的排序算法奠定了基础。

多年来，该算法不断得到改进，得到了各种计算机科学家和数学家的重要贡献。最早发表的关于合并排序算法的描述之一是约翰·莫奇利（John Mauchly）于 1945 年发表的“一种合并信息的方法”。格蕾丝·霍珀（Grace Hopper）在 20 世纪 50 年代为 UNIVAC I 计算机工作期间也为合并排序的发展做出了贡献。

在 20 世纪 60 年代，高德纳（Donald Knuth）在他的开创性著作《计算机程序设计艺术》（The Art of Computer Programming）的第一卷中收录了合并排序，巩固了其在排序算法经典中的地位。自那时以来，合并排序因其效率和稳定性而仍然是一种突出且广泛使用的排序算法。

算法概述

• 合并排序是一种分治算法，这意味着它将问题分解成更小的子问题，解决它们，然后将解决方案组合起来解决原始问题。合并排序算法的主要步骤可以概括如下：
• 分治：未排序的数组被分成两个（或更多）半部分，直到每个子数组只包含一个元素。这是递归的基本情况。
• 解决：子数组被递归地排序。这通常通过对每个子数组应用合并排序算法来完成，这涉及进一步的分割和排序。
• 合并：然后将已排序的子数组合并在一起，生成一个单一的已排序数组。这一步是算法名称的由来。

合并排序效率的关键在于合并步骤，它将已排序的子数组合并成一个单一的已排序数组。这个合并过程通过比较两个子数组的元素，并将它们按正确的顺序放入合并结果中来完成。这确保了元素在每个子数组中以及最终在整个已排序数组中的正确顺序。

递归性质

合并排序的递归性质是该算法的决定性特征。它反复地将问题分解成更小的子问题，直到达到基本情况，此时每个子数组只包含一个元素。此时，包含单个元素的子数组被认为已排序，然后算法开始合并子数组。

合并排序的递归结构可以看作是一个二叉树。在树的根部，是原始的未排序数组。随着递归的每个级别，数组被分成更小的子数组，形成一个二叉树结构。这棵树的叶子代表一个元素的子数组，它们本身就被定义为已排序。

合并排序时间复杂度

合并排序最吸引人的方面之一是其一致且高效的时间复杂度。合并排序在所有情况下都具有 O(n log n) 的时间复杂度，使其成为对大型数据集进行排序的可靠选择。让我们探讨一下原因：

• 分治：分治步骤包括反复将数组分成两半，直到我们得到单个元素的子数组。这个过程需要 O(log n) 的时间，因为在每一步数组都会被分成两半。
• 解决：在解决步骤中，每个子数组都独立排序。由于在合并过程中每个元素都被访问一次，因此对于每个递归级别，对子数组进行排序的时间复杂度为 O(n)。
• 合并：合并步骤需要 O(n) 的时间将大小为 n/2 的两个子数组合并成一个单一的已排序子数组。合并过程有效地组合了两个半部分，同时保持了元素的顺序。

综合考虑所有这些步骤，合并排序的总时间复杂度为 O(n log n)。这种一致且高效的性能是合并排序在实际中备受青睐的主要原因之一。

合并排序空间复杂度

算法的空间复杂度是指其执行期间使用的内存量。合并排序虽然在时间复杂度方面非常高效，但确实需要额外的内存来进行合并步骤。这使其成为一种稳定且自适应的排序算法，但不是原地排序算法。

合并排序的空间复杂度为 O(n)，这意味着它需要辅助内存来在合并步骤中存储两个子数组。这种辅助内存对于在合并过程中临时保存合并结果是必需的。实际上，这意味着合并排序消耗的额外内存与输入数据的大小成正比，在处理非常大的数据集时，这可能是一个需要考虑的问题。

但是，需要注意的是，合并排序使用的额外内存不依赖于输入数组中元素的具体排列，这使其稳定且自适应。稳定性是排序算法的一个理想属性，因为它确保相等的元素在排序输出中保持它们的相对顺序。

为了缓解空间复杂度问题，可以使用一种称为“自底向上”或“迭代”合并排序的替代方法。这种方法通过仔细管理合并过程和交换原始数组中的元素，将空间复杂度降低到 O(1)。虽然它提高了空间效率，但它可能不太直观，并且实现起来有些复杂。

合并排序实现

合并排序是一种多功能算法，可以用各种编程语言实现。为了说明其实现，让我们看一个 Python 的高级示例。此 C++ 实现遵循合并排序的算法步骤。

输出

Given array is 
12 11 13 5 6 7 
Sorted array is 
5 6 7 11 12 13 
................
Process executed in 1.11 seconds
Press any key to continue

解释

1. #include <bits/stdc++.h> and using namespace std;: 这些行包含必要的 C++ 标准库，并指定代码将使用标准命名空间以方便使用。
2. void merge(int array[], int const left, int const mid, int const right): 此函数负责合并输入数组的两个子数组。它接受三个参数：
   • array[]: 要排序的输入数组。
   • left: 第一个子数组的左索引。
   • mid: 分隔两个子数组的中间索引。
   • right: 第二个子数组的右索引。
3. merge 函数中的下一行：
   • 计算两个子数组的大小。
   • 创建临时数组 leftArray 和 rightArray 来存储两个子数组的数据。
   • 将原始数组中的数据复制到这些临时数组中。
4. merge 函数中的 while 循环通过比较两个子数组的元素并将它们按正确的顺序放入原始数组中来合并这两个子数组。
5. 合并后，有两个 while 循环将 leftArray 和 rightArray 中的任何剩余元素复制到原始数组中。
6. 最后，使用 delete[] 来释放为临时数组分配的内存。
7. void mergeSort(int array[], int const begin, int const end): 这是合并排序函数。它接受三个参数：
   • array[]: 要排序的输入数组。
   • begin: 要排序的子数组的左索引。
   • end: 要排序的子数组的右索引。
8. 在 mergeSort 函数中，如果 begin 大于或等于 end，则返回，因为在这种情况下没有需要排序的内容。
9. 该函数计算中间索引 mid，然后对左子数组和右子数组进行递归调用，最后使用 merge 函数将它们合并。
10. printArray 函数是一个用于打印数组元素的实用函数。
11. 在主函数中
    • 定义了一个示例整数数组 arr。
    • 使用 sizeof 计算数组大小。
    • 打印原始数组。
    • 调用 mergeSort 来排序数组。
    • 打印已排序的数组。

该代码演示了使用合并排序对整数数组进行排序的过程。

时间和空间复杂度

时间复杂度

合并排序是一种分治排序算法，其时间复杂度分析如下：

• 分治步骤：在此步骤中，数组被分成两个大小相等的子数组。此过程继续递归，直到我们得到大小为 1 的子数组。所需的分割次数约为 O(log n)，其中 n 是数组中的元素数量。
• 解决步骤：在解决步骤中，我们合并两个大小分别为 n/2 的子数组，这需要 O(n) 的时间。由于我们有 O(log n) 级别的递归，并且每个级别都需要 O(n) 的时间，因此合并操作的总时间复杂度为 O(n * log n)。
• 总体时间复杂度：分治步骤导致合并排序算法在最坏、最好和平均情况下的时间复杂度均为 O(n * log n)。这使得合并排序对于大型数据集非常高效。

空间复杂度

算法的空间复杂度是指执行算法所需的额外内存量。在合并排序代码的情况下，我们使用额外的内存用于以下目的：

• 临时数组：代码使用两个临时数组 leftArray 和 rightArray 来在合并步骤中存储子数组的元素。每个数组的大小约为 n/2。因此，这些临时数组的空间复杂度为 O(n)。
• 递归调用堆栈：合并排序是一种递归算法，每次递归调用都会创建一组新的局部变量和函数调用数据的内存。递归树的最大深度为 O(log n)，在每个级别，我们都有用于函数参数和局部变量的空间。调用堆栈中使用的总空间也为 O(log n)。
• 总体空间复杂度：合并排序的空间复杂度为 O(n)（用于临时数组）加上 O(log n)（用于调用堆栈）。因此，总体空间复杂度为 O(n + log n)，可以简化为 O(n)。

总之，合并排序算法在最坏、最好和平均情况下的时间复杂度为 O(n * log n)，空间复杂度为 O(n)。临时数组的使用和算法的递归性质有助于其空间复杂度。合并排序在时间复杂度方面效率很高，使其适合对大型数据集进行排序，但它确实需要额外的内存来运行。

归并排序的优点

• 稳定排序：合并排序是一种稳定排序算法，这意味着在排序过程中会保留相等元素的相对顺序。当基于多个标准对数据进行排序或需要保持相等元素的原始顺序时，这至关重要。
• 对大型数据集高效：合并排序在最坏、最好和平均情况下的时间复杂度均为 O(n log n)。这一特性使其对大型数据集的排序特别高效。与其他具有二次时间复杂度的算法（如冒泡排序或插入排序）不同，合并排序的性能随着输入尺寸的增加而不会显著下降。
• 保证性能：与其他一些排序算法不同，合并排序的时间复杂度无论数据分布如何，都保持不变。其分治策略确保它始终将数据分成平衡的分区，从而带来可预测的性能。
• 可并行性：合并排序可以利用并行处理来加速排序，使其适用于现代多核和分布式计算环境。通过将排序过程分解成更小的子问题，可以同时对这些子问题进行排序。
• 无最坏情况：合并排序不像快速排序那样存在最坏情况，在快速排序中，算法的性能可能会因特定数据分布而显著下降。其时间复杂度在所有情况下都稳定在 O (n log n)。

归并排序的缺点

• 空间复杂度：合并排序在合并阶段需要额外的内存来存储临时数组。这意味着其空间复杂度为 O(n)，在内存资源有限的情况下对非常大的数据集进行排序时，这可能是一个问题。
• 对小型数据集较慢：虽然合并排序对大型数据集非常高效，但其分治性质和函数调用的开销使其对于小型数据集来说相对于插入排序或选择排序等更简单的算法来说相对较慢。
• 非自适应：合并排序不会利用数据集中存在的任何现有顺序。即使数组已部分排序，合并排序仍将执行其标准的 D&C 方法，导致操作次数更多。
• 递归开销：合并排序通常使用递归来实现，由于函数调用和维护调用堆栈，这会增加一些开销。在某些编程语言或平台上，递归可能不是实现排序算法的最有效方式。

总而言之，合并排序的优点在于其效率、稳定性和可预测的性能，使其成为排序大型数据集以及需要稳定性的场景的绝佳选择。然而，其空间复杂度、非自适应性以及对小型数据集的较慢性能是值得注意的限制。在实践中，选择哪种排序算法取决于要排序的数据集的具体要求和特性。

合并排序的应用

合并排序是一种通用的排序算法，由于其效率和稳定性，在不同领域都有各种应用。其 O (n log n) 的时间复杂度以及在输入中保持相等元素相对顺序的能力使其非常适合许多任务。以下是合并排序的一些突出应用：

• 通用排序：合并排序通常用于各种应用程序中对大型数据集进行排序，例如数据库管理系统、文件处理和数据分析。其稳定的性质确保相等元素的原始顺序在排序输出中保持不变。
• 外部排序：合并排序非常适合对无法完全装入内存的大文件进行排序，这种情况称为外部排序。通过将数据分成可管理的块，对每个段进行排序，然后将它们合并在一起，合并排序最大限度地减少了对过多内存使用的需求。
• 并行处理：合并排序的分治性质非常适合并行化。不同的子数组可以在单独的处理器或线程上并行排序，从而利用多核架构来提高排序性能。
• 逆序计数：合并排序对于计数数组中的逆序非常有效，逆序表示一对顺序不正确的元素。这在测量两个序列之间的相似性或识别数据异常等应用中有用。
• 搜索算法：合并排序是各种搜索算法（如已排序数组中的二分搜索）的基本组成部分。通过确保数组保持排序状态，二分搜索可以有效地查找特定元素。
• 数据结构中的合并操作：合并排序的合并步骤也广泛用于数据结构操作中，例如合并两个已排序的链表或合并区间树中的区间。
• 基于合并的分治算法：许多高级算法，例如用于排序网络的合并排序，都使用合并技术作为构建块。这些算法通常在特定任务上表现出卓越的性能。
• 外部内存应用程序：合并排序广泛应用于处理存储在外部存储设备（如硬盘驱动器或固态驱动器）上的数据的应用程序中。它减少磁盘 I/O 操作次数的能力使其成为外部内存算法的重要组成部分。
• 数据库操作中的合并连接：在数据库系统中，合并排序用于合并连接操作，以根据特定条件有效地合并和检索两个已排序表中的数据。
• 离线算法：合并排序用于各种离线算法中，在这些算法中，在执行主算法之前，可以获取所有输入，从而进行有效的预处理。

总而言之，合并排序的效率、稳定性和对各种场景的适应性使其成为多个领域广泛使用且有价值的排序算法，涵盖从通用排序到复杂数据处理和存储应用程序。