Java 中使用多线程进行快速排序

快速排序是一种高效的“分而治之”的排序算法，它递归地将数组划分为更小的子数组。

多线程允许在不同分区上并行执行排序，利用多个处理器核心来减少执行时间。它允许程序的不同部分并发执行，以最大化CPU的利用率。

给定一个数组 arr。任务是使用多线程对数组进行快速排序。

示例 1

输入： arr = {10, 80, 30, 90, 40, 50, 70}

输出 [10, 30, 40, 50, 70, 80, 90]

解释： 枢轴 70 将数组划分为两个部分。 线程并行递归地对每个部分进行排序。

示例 2

输入： arr = {5, 2, 9, 1, 6, 3}

输出 [1, 2, 3, 5, 6, 9]

解释： 枢轴 3 对数组进行分区；递归调用并行排序左侧 {1,2} 和右侧 {5,6,9}。

示例 3

输入： arr = {12, 11, 13, 5, 6, 7}

输出 [5, 6, 7, 11, 12, 13]

解释： 枢轴 7 将元素分成 {5,6} 和 {11,12,13}，并在单独的线程中进行排序。

示例 4

输入： arr = {100, 50, 25, 75, 10, 5}

输出 [5, 10, 25, 50, 75, 100]

解释： 枢轴 25 将元素分成 {5,10} 和 {50,75,100}，并使用并行线程进行排序。

方法 1：基本多线程快速排序（使用两个线程）

该方法创建两个独立的线程以并行排序左侧和右侧分区。

算法

步骤 1： 选择一个枢轴元素（在此示例中为最后一个元素）。

步骤 2： 对数组进行分区，使小于或等于枢轴的元素位于左侧，较大的元素位于右侧。

步骤 3： 使用单独的线程递归地对左侧和右侧分区进行排序。

步骤 4： 使用 start() 方法启动每个线程，并使用 join() 方法确保排序完成后再继续。

输出

 
Sorted Array: [10, 30, 40, 50, 70, 80, 90]   

时间复杂度： 由于枢轴选择和递归深度，程序的 O(n log n) 时间复杂度。

空间复杂度：由于递归堆栈调用，程序的 O(n) 空间复杂度。