java - 多线程归并排序问题

Question

我正在尝试编写一个多线程合并排序，但我遇到了一些对我来说非常令人困惑的问题。我不完全了解线程如何共享/使用变量的规则...

例如，如果在一个可运行类中，我创建了该可运行类的另一个实例并将其作为参数传递给我的数组之一，那么该类的编辑是否会进行传输？看起来他们确实这么做了，但我也似乎有意想不到的行为。

这是我的代码:

public class PSort implements Runnable {

private int [] Arr;
private int begin;
private int end;

public void run () {
    // Base Case - Insertion sort
    if(this.end-this.begin <= 10) {
        InsertionSort();
    }
    else {
        int left_start  = this.begin;
        int left_end    = this.begin + (this.end-this.begin)/2;
        int right_start = this.begin + (this.end-this.begin)/2 + 1;
        int right_end   = this.end;


        Thread t1 = new Thread(new PSort(this.Arr, left_start, left_end));
        Thread t2 = new Thread(new PSort(this.Arr, right_start, right_end));
        t1.start();
        t2.start();

        try {
            t1.join();
            t2.join();

            merge(left_start, left_end, right_start, right_end);
        } catch (Exception e) {}
    }
}

public PSort (int[] A, int begin, int end) {
    this.Arr = A;
    this.begin = begin;
    this.end = end;
    System.out.println("New thread: " + this.begin + " " + this.end);
}

public static void ParallelSort (int[] A, int begin, int end) {

    PSort psort = new PSort(A, begin, end);
    Thread thread = new Thread(psort);

    thread.start();

    try {
        thread.join();
        psort.printArray();
    } catch (InterruptedException e) {}
}

public void printArray() {
    int count = 0;
    for(int x = this.begin; x < this.end; x++) {
        if(count < 10) {
            System.out.print(Arr[x] + " ");
            count++;
        }
        else {
            count = 1;
            System.out.print("\n" + Arr[x] + " ");
        }
    }
}

private void InsertionSort () {
    for(int x = this.begin; x < this.end; x++) {
        int currentNum = this.Arr[x];
        int hole = x;
        while((hole > 0) && (this.Arr[hole-1] > currentNum)) {
            this.Arr[hole] = this.Arr[hole-1];
            hole = hole - 1;
        }
        this.Arr[hole] = currentNum;
    }
}

private void merge (int left_start, int left_end, int right_start, int right_end) {
    /*
    int length = right_end - left_start;

    int[] temp = new int[length];
    int leftP = left_start;
    int rightP = right_start;
    int index = 0;

    while((leftP <= left_end) && (rightP < right_end)) {
        if(Arr[leftP] < Arr[rightP]) {
            temp[index++] = Arr[leftP++];
        }
        else {
            temp[index++] = Arr[rightP++];
        }
    }   
    while(leftP <= left_end) {
        temp[index++] = Arr[leftP++];
    }
    while(rightP < right_end) {
        temp[index++] = Arr[rightP++];
    }

    System.arraycopy(temp, 0, Arr, left_start, length);
    */

}
}

现在，我使用填充有随机整数 0-9 的大小为 40 的数组调用 PSort.ParallelSort，这是我得到的输出:

New thread: 0 40
New thread: 0 20
New thread: 21 40
New thread: 0 10
New thread: 11 20
New thread: 21 30
New thread: 31 40
0 1 1 2 2 2 6 7 7 8 
8 3 3 3 4 4 5 5 6 7 
9 2 3 3 3 4 7 8 9 9 
2 2 6 7 7 7 8 8 9 9 

请注意，我已经注释掉了例程的“合并”部分，因此我希望输出的每一行都能正确排序，但事实并非如此。我单独测试了插入排序，它似乎从来没有失败过，所以这里似乎存在一些我完全忽略的并发问题。

注意:我意识到这里存在一些更严重的问题，因为较高的数字被加权到整个数组的最后两行，即使我没有合并......

Answer 1

该错误存在于您的 InsertionSort 方法中(顺便说一句，该方法的命名应以小写字母开头):

int hole = x;
while ((hole > 0) && /* ... */) {
    // ...
    hole--;
}

因此，您从位于指定段内的 x 开始，但返回到 0，因此所有线程最终都会在同一段上写入。是的，数据在线程之间共享，这就是多线程时的困难。