如何用多线程正确查找未排序数组中的第k小元素？

问题核心 #

你当前的实现逻辑存在根本性错误：直接对每个子数组查找原数组的k值对应的元素，最终收集的子数组结果与整体数组的第k小元素没有关联。比如你给出的例子中，原数组第3小元素是3，但你让每个长度为3的子数组查找第3小（即子数组最大值），得到的[7,9,8]自然和正确答案无关。

错误点拆解 #

1. 参数传递错误：创建SearchingItemThread时，传入的target是原数组的k值，但每个子数组的长度远小于原数组长度，此时查找子数组的第target小元素没有意义。
2. 逻辑链断裂：收集完子数组的结果后，没有进行后续的合并计算，直接输出的结果无法反映整体数组的第k小元素。

可行的多线程解决方案 #

方案一：并行排序子数组 + 多路归并找第k小 #

这是实现起来较简单的方案，核心思路是：

• 多线程并行排序各个子数组，减少排序耗时
• 对所有有序子数组执行多路归并，找到整体第k小元素

修改后的代码实现

import java.util.*;
import java.util.concurrent.CountDownLatch;

// 负责排序子数组的线程类
class SortSubarrayThread implements Runnable {
    private int[] subarray;
    private CountDownLatch latch;

    public SortSubarrayThread(int[] subarray, CountDownLatch latch) {
        this.subarray = subarray;
        this.latch = latch;
    }

    @Override
    public void run() {
        Arrays.sort(subarray);
        latch.countDown();
    }

    public int[] getSortedSubarray() {
        return subarray;
    }
}

public class KthSmallestMultiThread {
    public int findResultByMultithreading(int numberOfThreads, List<Integer> list, int k) {
        // 注意：这里假设k是1-based，若为0-based需调整
        int targetIndex = k - 1;
        int[] arr = list.stream().mapToInt(Integer::intValue).toArray();
        int[][] subArrays = splitArray(arr, numberOfThreads);

        CountDownLatch latch = new CountDownLatch(numberOfThreads);
        SortSubarrayThread[] threads = new SortSubarrayThread[numberOfThreads];

        // 启动多线程排序子数组
        for (int i = 0; i < numberOfThreads; i++) {
            threads[i] = new SortSubarrayThread(subArrays[i], latch);
            new Thread(threads[i]).start();
        }

        // 等待所有子数组排序完成
        try {
            latch.await();
        } catch (InterruptedException e) {
            Thread.currentThread().interrupt();
            throw new RuntimeException("线程中断", e);
        }

        // 收集所有有序子数组
        List<int[]> sortedSubarrays = new ArrayList<>();
        for (SortSubarrayThread thread : threads) {
            sortedSubarrays.add(thread.getSortedSubarray());
        }

        // 多路归并找第targetIndex小的元素
        return findKthInSortedArrays(sortedSubarrays, targetIndex);
    }

    // 拆分数组为多个子数组
    private int[][] splitArray(int[] arr, int splitCount) {
        int[][] subArrays = new int[splitCount][];
        int subSize = arr.length / splitCount;
        for (int i = 0; i < splitCount; i++) {
            int start = i * subSize;
            int end = (i == splitCount - 1) ? arr.length : (i + 1) * subSize;
            subArrays[i] = Arrays.copyOfRange(arr, start, end);
        }
        return subArrays;
    }

    // 多路归并找第k小元素（k为0-based）
    private int findKthInSortedArrays(List<int[]> sortedArrays, int k) {
        int[] pointers = new int[sortedArrays.size()];
        int count = 0;
        int result = 0;

        while (count <= k) {
            int minVal = Integer.MAX_VALUE;
            int minIndex = -1;

            // 找到当前所有子数组指针位置的最小值
            for (int i = 0; i < sortedArrays.size(); i++) {
                int[] arr = sortedArrays.get(i);
                if (pointers[i] < arr.length && arr[pointers[i]] < minVal) {
                    minVal = arr[pointers[i]];
                    minIndex = i;
                }
            }

            result = minVal;
            pointers[minIndex]++;
            count++;
        }

        return result;
    }

    // 测试示例
    public static void main(String[] args) {
        KthSmallestMultiThread solver = new KthSmallestMultiThread();
        List<Integer> list = Arrays.asList(4, 7, 2, 9, 5, 1, 6, 8, 3);
        int k = 3;
        int result = solver.findResultByMultithreading(3, list, k);
        System.out.println("第" + k + "小元素：" + result); // 输出3
    }
}

方案二：并行化Quickselect算法 #

如果追求更高的效率（避免全排序的开销），可以实现并行版的Quickselect，核心思路是：

1. 随机选择一个pivot元素
2. 多线程分段统计数组中小于、等于、大于pivot的元素数量
3. 根据统计结果，确定第k小元素所在的分区，递归在对应分区中继续查找

这种方案的优势是无需全排序，平均时间复杂度更优，但实现复杂度较高。

总结 #

• 不需要先对每个子数组排序再整体排序，而是排序子数组后通过多路归并直接定位第k小元素
• 若追求效率，优先考虑并行化Quickselect；若追求实现简单，选择并行排序+多路归并即可

内容的提问来源于stack exchange，提问作者Svitlana Vorobets