Java 中使用多线程进行归并排序

归并排序是一种流行的排序算法，通过将数组或列表划分为更小的子数组，对它们进行独立排序，然后将它们重新合并，从而有效地对其进行排序。它以其有效性、稳定性和处理大型数据集的能力而闻名。通过在 Java 中使用多线程，我们可以将工作负载分配给多个线程并并行执行它们，从而提高归并排序的性能。

Java 的多线程功能允许在单个程序中执行多个线程，每个线程代表一个独立的代码执行流。通过使用多个线程，我们可以利用可用的处理能力来加速排序操作。多线程归并排序的基本思想是将输入数组分成更小的块，并将每个块分配给自己的线程进行排序。一旦各个部分被排序，我们就将它们合并起来以获得最终排序的数组。

示例

输入 {9, 2, 5, 1, 7, 4, 8, 3, 6, 11, 15, 12, 13, 10, 14}

输出 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]

算法

步骤 1：创建一个名为 MultithreadedMergeSort 的类，其中包含私有实例变量 array 和 tempArray，类型为 int[]。

步骤 2：在 MultithreadedMergeSort 类中实现一个公共方法 sort(int[] inputArray)。此方法将负责启动排序过程。

步骤 3：在 sort() 方法中

步骤 3.1：将 inputArray 分配给 array 实例变量。

步骤 3.2：将 tempArray 的长度初始化为与 inputArray 相同。

步骤 4：在 MultithreadedMergeSort 类中实现一个私有方法 mergeSort(int low, int high)。此方法将使用递归处理实际的排序过程。

步骤 5：在 mergeSort() 方法中

步骤 5.1：检查 low 是否小于 high，以确保当前子数组包含多个元素。

步骤 5.2：将 mid 索引计算为 low 和 high 的平均值。

步骤 6：使用 Thread 类和 lambda 表达式创建两个独立的线程来排序子数组的左半部分和右半部分。

步骤 6.1：创建一个 leftThread，它为左半部分递归调用 mergeSort()，并将 low 和 mid 作为参数传递。

步骤 6.2：创建一个 rightThread，它为右半部分递归调用 mergeSort()，并将 mid + 1 和 high 作为参数传递。

步骤 7：使用 start() 方法启动这两个线程。

步骤 8：在两个线程上使用 join() 方法，等待它们完成，然后再继续。

步骤 9：线程完成后，调用 merge() 方法合并已排序的部分。

步骤 10：在 MultithreadedMergeSort 类中实现一个私有方法 merge(int low, int mid, int high)。此方法将两个已排序的部分合并回原始数组。

步骤 11：在 merge() 方法中

步骤 11.1：使用 System.arraycopy() 将两个部分复制到临时数组中。

步骤 11.2：将 leftIndex 初始化为 low，将 rightIndex 初始化为 mid + 1，将 currentIndex 初始化为 low。

步骤 11.3：比较两个部分中的元素，并将它们按升序合并回原始数组。

步骤 11.4：如果还有剩余元素，则将左半部分或右半部分的剩余元素复制过来。

步骤 12：在 main() 方法中

步骤 12.1：创建 MultithreadedMergeSort 的一个实例。

步骤 12.2：声明并初始化一个输入数组。

步骤 12.3：在 MultithreadedMergeSort 实例上调用 sort() 方法，并将输入数组传递给它。

步骤 12.4：使用 Arrays.toString() 打印排序后的数组。

实施

上述步骤的实现如下

文件名： MultithreadedMergeSort.java

输出

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]

复杂度分析

多线程归并排序的时间复杂度与常规归并排序算法相同，即 O(n log n)，其中“n”是输入数组中的元素数量。

多线程归并排序的空间复杂度为 O(n)，其中“n”是输入数组中的元素数量。