并行排序与Arrays.sort()输出不一致问题排查求助

我尝试用线程实现改进版插入排序，目标是将数组前k个元素按降序排序（第0位最大，第k-1位最小），但排序后的para_array与Arrays.sort()降序处理的结果有时一致、有时不一致。不一致时的对比结果如下：

99940 and 99941
99938 and 99940
99935 and 99938
99934 and 99935
99932 and 99934

（左侧为para_array前k个元素，右侧为Arrays.sort()降序后的对应值）

排序前已用相同随机种子（random(7363)）填充两个数组，初始值完全一致。以下是我的实现代码及问题分析、修复方案：

原实现代码 #

1. 串行排序前k个元素 #

//sort the k first where 0 is largest number and k-1 is lowest
for (int i = 1; i < k; i++) {
    int check = para_array[i];
    int prev = i - 1;
    while (prev >= 0 && para_array[prev] < check) {
        para_array[prev + 1] = para_array[prev];
        previous_element--; // 变量名错误
    }
    para_array[prev + 1] = check;
}

2. 线程实现类 #

public SortingThread(int[] arr, int start, int end, int k, Object lock) {
    this.arr = arr;
    this.start = start;
    this.end = end;
    this.k = k;
    this.lock = lock;
}

@Override
public void run() {
    for (int i = start; i < end; i++) {
        synchronized (lock) {
            if (arr[i] > arr[k - 1]) {
                int set_correct = arr[i];
                int j = k - 2;
                while (j >= 0 && arr[j] < set_correct) {
                    arr[j + 1] = arr[j];
                    j--;
                }
                arr[j + 1] = set_correct;
            }
        }
    }
}

3. 线程创建与启动 #

// Create and start all the threads
for (int i = 0; i < number_of_cores; i++) {
    int start = i * portionSize;
    int end = Math.min((i + 1) * portionSize, n);
    threads.add(new SortingThread(para_array, start, end, k, locks.get(i)));
}

for (Thread t : threads) {
    t.start();
}

问题根源 #

1. 串行排序变量错误：while循环中误用了未定义的previous_element变量，导致初始前k个元素排序逻辑完全错误，这是结果混乱的基础原因。
2. 并发锁失效：每个线程使用独立的lock对象，多个线程可同时修改前k个元素的区域，并发修改会互相覆盖，导致数据不一致。
3. 未等待线程完成：启动线程后直接对比结果，部分线程可能还未执行完毕，para_array处于中间状态。

修复方案 #

1. 修正串行排序变量 #

把previous_element--改为prev--，确保初始排序逻辑正确：

for (int i = 1; i < k; i++) {
    int check = para_array[i];
    int prev = i - 1;
    while (prev >= 0 && para_array[prev] < check) {
        para_array[prev + 1] = para_array[prev];
        prev--; // 修正变量名
    }
    para_array[prev + 1] = check;
}

2. 使用全局锁保证并发安全 #

所有线程共享同一个锁对象，确保同一时间只有一个线程修改前k个元素区域：

// 创建全局锁
Object globalLock = new Object();

// 创建线程时传入全局锁
for (int i = 0; i < number_of_cores; i++) {
    int start = i * portionSize;
    int end = Math.min((i + 1) * portionSize, n);
    threads.add(new SortingThread(para_array, start, end, k, globalLock));
}

3. 等待所有线程执行完毕 #

启动线程后调用join()等待所有线程完成，再进行结果对比：

for (Thread t : threads) {
    t.start();
}

// 等待所有线程执行完成
for (Thread t : threads) {
    try {
        t.join();
    } catch (InterruptedException e) {
        e.printStackTrace();
    }
}

验证效果 #

修复后，para_array的前k个元素将与Arrays.sort()降序处理后的结果完全一致，不会再出现随机不一致的问题。

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