java - 使用阈值的多线程冒泡

Question

所以我得到了这个任务，我必须将一个数组拆分为两个，将拆分后的数组拆分为2，依此类推...直至达到某个阈值。

因此，如果我的阈值是1000，那将是:
10k> 2x 5k> 4x 2500> 8x 1250> 16x 625(数组中的数字)。

然后，我必须对这些数组进行排序并合并它们:
16x 625(合并)> 8x 1250(合并)> 4x 2500(合并)> 2x 5000(合并)> 1x 10k。
所有这些都必须保持排序。

所以我认为我已经走得很远了，但是它似乎并没有按照我想要的方式工作。我尝试了多种方法来找出出了什么问题，但是我还没有弄清楚这就是为什么我在这里。

有人可以帮助我了解我做错了什么并给我解决方案吗？

Bubblesort.java:

package PartThree;

import java.util.ArrayList;
import java.util.List;

public class Bubblesort implements Runnable {
public List<Integer> arrayList;
private int threshold;
private int middle;

public Bubblesort(List<Integer> arrayList, int threshold) {
    this.arrayList = arrayList;
    this.threshold = threshold;
    this.middle = arrayList.size() / 2;
    System.out.println(arrayList.size() + " ha");
}

@Override
public void run() {
    if (arrayList.size() <= treshold) {
        sort();
    }else if(threshold<arrayList.size()){
        Bubblesort rLeft = new Bubblesort(arrayList.subList(0, middle), threshold);
        Bubblesort rRight = new Bubblesort(arrayList.subList(middle, arrayList.size()), threshold);


        Thread tLeft = new Thread(rLeft);
        Thread tRight = new Thread((rRight));
        tRight.start();
        tLeft.start();
        try {
            tLeft.join();
            tRight.join();
        } catch (InterruptedException e) {
            e.printStackTrace();
        }

        merge(rLeft.arrayList, rRight.arrayList);
        System.out.println(arrayList.size() + ":size");
    }
}

private void merge(List<Integer> left, List<Integer> right) {
    int i = 0, j = 0, k = 0;
    List<Integer> temp = new ArrayList<>();
    while (i < left.size() && j < right.size()) {
        if (left.get(i) < right.get(j)) {
            temp.add(k, left.get(i));
            i++;
        } else {
            temp.add(k, right.get(j));
            j++;
        }
        k++;
    }
    while (i < left.size()) {
        temp.add(k, left.get(i));
        i++;
        k++;
    }
    while (j < right.size()) {
        temp.add(k, right.get(j));
        j++;
        k++;
    }
    arrayList = temp;
    temp.clear();
}

private void sort() {
    int i, j, tijdelijk;
    for (j = 0; j < arrayList.size(); j++) {
        for (i = 1; i < arrayList.size() - j; i++) {
            if (arrayList.get(i - 1) > arrayList.get(i)) {
                tijdelijk = arrayList.get(i);
                arrayList.set(i, arrayList.get(i - 1));
                arrayList.set(i - 1, tijdelijk);
            }
        }
    }
}
}

实现:

package PartThree;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

public class API {
private Random random = new Random();
private List<Integer> array_unsorted_main = new ArrayList<>();
private int maxSize;

private Thread t1;

private void run(){
    this.maxSize = 10000;

    for (int i = 0; i < maxSize; i++) {
        array_unsorted_main.add(random.nextInt(10000));
    }
    t1 = new Thread(new Bubblesort(array_unsorted_main,1000));
    t1.start();
    try {
        t1.join();
    } catch (InterruptedException e) {
        e.printStackTrace();
    }

}

    public static void main(String args[]){
        new PartThree.API().run();
    }
}

请帮帮我，谢谢您的时间。

Answer 1

您的问题之一是在merge方法中先执行arrayList = temp;，然后再进行temp.clear()，从而清除arrayList，因为它现在指向temp。

删除temp.clear()语句，以便arrayList将保留排序后的值。