归并排序及其Java并发实现

冒泡排序

因为在归并排序的简化过程中需要用到冒泡排序，所以这里先做一下简单介绍。

冒泡排序（Bubble Sort），是一种计算机科学领域的较简单的排序算法。

它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。

这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端，故名。

算法原理

  • 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
  • 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
  • 针对所有的元素重复以上的步骤，除了最后一个。
  • 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

时间复杂度

冒泡排序的最优时间复杂度为：\(O(n)\)

最坏时间复杂度为：\(O(n^2)\)

平均时间复杂度为：\(O(n^2)\)

示例代码

public static void BubbleSort(Integer[] list) {
    for (int i = 0; i < list.length; i++) {
        for (int j = i + 1; j < list.length; j++) {
            if (list[i] > list[j]) {
                swap(list, i, j);
            }
        }
    }
}

在归并排序中用到的是冒泡排序的修改版，多了两个参数first和last，只对数组中索引从first到last的元素进行冒泡排序，示例代码如下。

public static void BubbleSort(
        Integer[] list,
        int first,
        int last) {
    for (int i = first; i <= last; i++) {
        for (int j = i + 1; j <= last; j++) {
            if (list[i] > list[j]) {
                swap(list, i, j);
            }
        }
    }
}

归并排序

归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

算法原理

归并操作的工作原理如下：

  • 第一步：申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
  • 第二步：设定两个指针，最初位置分别为两个已经排序序列的起始位置
  • 第三步：比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
  • 重复步骤3直到某一指针超出序列尾
  • 将另一序列剩下的所有元素直接复制到合并序列尾

时间复杂度

时间复杂度为\(O(nlog₂n)\) 这是该算法中最好、最坏和平均的时间性能。

空间复杂度为 \(O(n)\)

比较操作的次数介于\((nlogn) / 2\)和\(nlogn – n + 1\)。

赋值操作的次数是\((2nlogn)\)。

归并算法的空间复杂度为：\(O (n)\)

归并排序比较占用内存，但却是一种效率高且稳定的算法。

示例代码

public static void MergeArray(
        Integer[] list,
        int first,
        int mid,
        int last) {
    int i = first;
    int j = mid + 1;
    int m = mid;
    int n = last;
    ArrayList<Integer> tmp = new ArrayList<>(
            last - first + 1);
    while (i <= m && j <= n) {
        if (list[i] <= list[j]) {
            tmp.add(list[i++]);
        } else {
            tmp.add(list[j++]);
        }
    }
    while (i <= m) {
        tmp.add(list[i++]);
    }
    while (j <= n) {
        tmp.add(list[j++]);
    }
    for (int index = 0; index < tmp.size(); index++) {
        list[first + index] = tmp.get(index);
    }
}

public static void MergeSort(
    Integer[] list,
    int first,
    int last) {
    if (first < last) {
        int mid = (first + last) / 2;
        MergeSort(list, first, mid);
        MergeSort(list, mid + 1, last);
        MergeArray(list, first, mid, last);
    }
}

归并排序升级版

下图是对1到100个随机数字进行排序，冒泡排序和归并排序运行的时间比较。（单位：秒）

可以看出，虽然归并排序的运行时间小于冒泡排序，但是在排序数字数目较少时（20个以下），冒泡排序的性能要优于归并排序，由此得出以下归并排序的升级版：

设置一个阈值min，当需要排序的数字数目大于min时，继续归并排序；反之，当需要排序的数字数目小于min时，进行冒泡排序。

示例代码如下，这里设置min为需要传入的参数。

public static void MergeSort2(
        Integer[] list,
        int first,
        int last,
        int min) {
    if (last - first > min) {
        int mid = (first + last) / 2;
        MergeSort(list, first, mid);
        MergeSort(list, mid + 1, last);
        MergeArray(list, first, mid, last);
    } else {
        BubbleSort(list, first, last);
    }
}

下面分别对传入参数min为3，4，5，6时对1到100000个随机数字进行排序的运行时间比较。（单位：秒）

放大图像的右下部分。

由于随机数字不稳定的原因，min的不同取值造成的运行时间影响也有所不同。这里的升级版本采取稳定性较好的min=5，示例代码如下。

public static void MergeSort3(
        Integer[] list,
        int first,
        int last) {
    if (last - first > 5) {
        int mid = (first + last) / 2;
        MergeSort(list, first, mid);
        MergeSort(list, mid + 1, last);
        MergeArray(list, first, mid, last);
    } else {
        BubbleSort(list, first, last);
    }
}

归并排序并发实现

对于归并排序考虑到以下问题：

既然把一个排序问题递归地分解成两个更小的排序问题，那么可不可以将这两个排序分别在不同线程中进行呢，答案当然是可以的。

下面使用两种方式进行实现，分别使用Callable/Future和Fork/Join框架，在两个线程中分别进行二路分解，当两个线程都分解完成时，再启用归并程序。（这里都采用上面得到的最优归并排序策略MergeSort3）

Callable/Future实现示例代码如下。

public static class MergeSort4 implements Callable<Boolean> {
    private ExecutorService threadPool;
    private Future<Boolean> loadResult0;
    private Future<Boolean> loadResult1;
    private Integer[] list;
    private int first;
    private int last;

    public MergeSort4(Integer[] list, ExecutorService threadPool) {
        this.list = list;
        this.threadPool = threadPool;
        first = 0;
        last = list.length - 1;
    }

    public MergeSort4(Integer[] list, int first, int last,
                      ExecutorService threadPool) {
        this.list = list;
        this.first = first;
        this.last = last;
        this.threadPool = threadPool;
    }

    /**
     * Computes a result, or throws an exception if unable to do so.
     *
     * @return computed result
     * @throws Exception if unable to compute a result
     */
    @Override
    public Boolean call() throws Exception {
        if (last - first > 5) {
            int mid = (first + last) / 2;
            loadResult0 = threadPool.submit(
                    new MergeSort4(list, first, mid, threadPool)
            );
            loadResult1 = threadPool.submit(
                    new MergeSort4(list, mid + 1, last, threadPool)
            );
            try {
                if (loadResult0.get() && loadResult1.get()) {
                    MergeArray(list, first, mid, last);
                }
            } catch (InterruptedException e) {
                e.printStackTrace();
            } catch (ExecutionException e) {
                e.printStackTrace();
            }
        } else {
            BubbleSort(list, first, last);
        }
        return true;
    }
}

Fork/Join实现示例代码如下。

public static class MergeSort5 extends RecursiveTask {
    private Integer[] list;
    private int first;
    private int last;

    public MergeSort5(Integer[] list) {
        this.list = list;
        first = 0;
        last = list.length - 1;
    }

    public MergeSort5(Integer[] list, int first, int last) {
        this.list = list;
        this.first = first;
        this.last = last;
    }

    /**
     * The main computation performed by this task.
     *
     * @return the result of the computation
     */
    @Override
    protected Object compute() {
        if (last - first > 5) {
            int mid = (first + last) / 2;
            MergeSort5 leftTask = new MergeSort5(list, first, mid);
            MergeSort5 rightTask = new MergeSort5(list, mid + 1, last);
            leftTask.fork();
            rightTask.fork();
            leftTask.join();
            rightTask.join();
            MergeArray(list, first, mid, last);
        } else {
            BubbleSort(list, first, last);
        }
        return null;
    }
}

Fork/Join框架详解

Fork/Join框架介绍

Fork/Join框架是Java7提供了的一个用于并行执行任务的框架， 是一个把大任务分割成若干个小任务，最终汇总每个小任务结果后得到大任务结果的框架。

我们再通过Fork和Join这两个单词来理解下Fork/Join框架，Fork就是把一个大任务切分为若干子任务并行的执行，Join就是合并这些子任务的执行结果，最后得到这个大任务的结果。比如计算1+2+……＋10000，可以分割成10个子任务，每个子任务分别对1000个数进行求和，最终汇总这10个子任务的结果。当然，也可以分成更多更小的任务。

Fork/Join框架设计

第一步分割任务。首先我们需要有一个fork类来把大任务分割成子任务，有可能子任务还是很大，所以还需要不停的分割，直到分割出的子任务足够小。

第二步执行任务并合并结果。分割的子任务分别放在双端队列里，然后几个启动线程分别从双端队列里获取任务执行。子任务执行完的结果都统一放在一个队列里，启动一个线程从队列里拿数据，然后合并这些数据。

Fork/Join使用两个类来完成以上两件事情：

  • ForkJoinTask：我们要使用ForkJoin框架，必须首先创建一个ForkJoin任务。它提供在任务中执行fork()和join()操作的机制，通常情况下我们不需要直接继承ForkJoinTask类，而只需要继承它的子类，Fork/Join框架提供了以下两个子类：
    • RecursiveAction：用于没有返回结果的任务。
    • RecursiveTask：用于有返回结果的任务。
  • ForkJoinPool：ForkJoinTask需要通过ForkJoinPool来执行，任务分割出的子任务会添加到当前工作线程所维护的双端队列中，进入队列的头部。当一个工作线程的队列里暂时没有任务时，它会随机从其他工作线程的队列的尾部获取一个任务。

Fork/Join框架使用

让我们通过一个简单的需求来使用下Fork/Join框架，需求是：计算1+2+3+4的结果。

使用Fork/Join框架首先要考虑到的是如何分割任务，如果我们希望每个子任务最多执行两个数的相加，那么我们设置分割的阈值是2，由于是4个数字相加，所以Fork/Join框架会把这个任务fork成两个子任务，子任务一负责计算1+2，子任务二负责计算3+4，然后再join两个子任务的结果。

因为是有结果的任务，所以必须继承RecursiveTask，实现代码如下：

public static class CountTask extends RecursiveTask {
    private static final int THRESHOLD = 2;
    private int start;
    private int end;

    public CountTask(int start, int end) {
        this.start = start;
        this.end = end;
    }

    /**
     * The main computation performed by this task.
     *
     * @return the result of the computation
     */
    @Override
    protected Integer compute() {
        int sum = 0;
        boolean canCompute = (end - start) <= THRESHOLD;
        if (canCompute) {
            for (int i = start; i <= end; i++) {
                sum += i;
            }
        } else {
            int middle = (start + end) / 2;
            CountTask leftTask = new CountTask(start, middle);
            CountTask rightTask = new CountTask(middle + 1, end);
            leftTask.fork();
            rightTask.fork();
            int leftResult = (int) leftTask.join();
            int rightResult = (int) rightTask.join();
            sum = leftResult + rightResult;
        }
        return sum;
    }
}

这个类是通用的计算1+2+……＋n，每次取两个数相加，当传入参数1和4时，为计算1+2+3+4的结果。

附录1：产生一定数量随机数字的方法

public static Integer[] RandomList(int num) {
    ArrayList<Integer> list = new ArrayList<>(num);
    for (int i = 0; i < num; i++) {
        list.add(i);
    }
    Collections.shuffle(list);
    return list.toArray(new Integer[num]);
}

附录2：交换数组中两个索引的元素的方法

public static void swap(Integer[] list, int index1, int index2) {
    int tmp = list[index1];
    list[index1] = list[index2];
    list[index2] = tmp;
}

附录3：主函数（测试程序）

其中range（delta，maxNum+delta，delta）是测试的数组元素数目的取值集合。

public static void main(String[] args) {
    File file = new File("MergeSort.txt");
    try {
        System.setOut(new PrintStream(file));
    } catch (FileNotFoundException e) {
        e.printStackTrace();
    }

    int maxNum = 100000;
    int delta = 100;
    int listNum = 10000;
    long lastTime, curTime, nsPerTime;
    Integer[] list;

    System.out.println("BubbleSort");
    for (listNum = delta; listNum <= maxNum; listNum += delta) {
        list = RandomList(listNum);
        lastTime = System.nanoTime();
        BubbleSort(list);
        curTime = System.nanoTime();
        nsPerTime = curTime - lastTime;
        System.out.print(nsPerTime / 1.0E9 + ",");
    }
    System.out.println();

    System.out.println("MergeSort");
    for (listNum = delta; listNum <= maxNum; listNum += delta) {
        list = RandomList(listNum);
        lastTime = System.nanoTime();
        MergeSort(list, 0, list.length - 1);
        curTime = System.nanoTime();
        nsPerTime = curTime - lastTime;
        System.out.print(nsPerTime / 1.0E9 + ",");
    }
    System.out.println();

    System.out.println("MergeSort 3");
    for (listNum = delta; listNum <= maxNum; listNum += delta) {
        list = RandomList(listNum);
        lastTime = System.nanoTime();
        MergeSort2(list, 0, list.length - 1, 3);
        curTime = System.nanoTime();
        nsPerTime = curTime - lastTime;
        System.out.print(nsPerTime / 1.0E9 + ",");
    }
    System.out.println();

    System.out.println("MergeSort 4");
    for (listNum = delta; listNum <= maxNum; listNum += delta) {
        list = RandomList(listNum);
        lastTime = System.nanoTime();
        MergeSort2(list, 0, list.length - 1, 4);
        curTime = System.nanoTime();
        nsPerTime = curTime - lastTime;
        System.out.print(nsPerTime / 1.0E9 + ",");
    }
    System.out.println();

    System.out.println("MergeSort 5");
    for (listNum = delta; listNum <= maxNum; listNum += delta) {
        list = RandomList(listNum);
        lastTime = System.nanoTime();
        MergeSort2(list, 0, list.length - 1, 5);
        curTime = System.nanoTime();
        nsPerTime = curTime - lastTime;
        System.out.print(nsPerTime / 1.0E9 + ",");
    }
    System.out.println();

    System.out.println("MergeSort 6");
    for (listNum = delta; listNum <= maxNum; listNum += delta) {
        list = RandomList(listNum);
        lastTime = System.nanoTime();
        MergeSort2(list, 0, list.length - 1, 6);
        curTime = System.nanoTime();
        nsPerTime = curTime - lastTime;
        System.out.print(nsPerTime / 1.0E9 + ",");
    }
    System.out.println();

    System.out.println("MergeSort Callable");
    for (listNum = delta; listNum <= maxNum; listNum += delta) {
        list = RandomList(listNum);
        ExecutorService threadPool = Executors.newCachedThreadPool();
        MergeSort4 mergeSort4 = new MergeSort4(list, threadPool);
        lastTime = System.nanoTime();
        Future<Boolean> result = threadPool.submit(mergeSort4);
        try {
            result.get();
        } catch (InterruptedException e) {
            e.printStackTrace();
        } catch (ExecutionException e) {
            e.printStackTrace();
        } finally {
            threadPool.shutdown();
        }
        curTime = System.nanoTime();
        nsPerTime = curTime - lastTime;
        System.out.print(nsPerTime + ",");
    }
    System.out.println();

    System.out.println("MergeSort RecursiveTask");
    for (listNum = delta; listNum <= maxNum; listNum += delta) {
        list = RandomList(listNum);
        ForkJoinPool forkJoinPool = new ForkJoinPool();
        MergeSort5 mergeSort5 = new MergeSort5(list);
        lastTime = System.nanoTime();
        Future result = forkJoinPool.submit(mergeSort5);
        try {
            result.get();
        } catch (InterruptedException e) {
            e.printStackTrace();
        } catch (ExecutionException e) {
            e.printStackTrace();
        } finally {
            forkJoinPool.shutdown();
        }
        curTime = System.nanoTime();
        nsPerTime = curTime - lastTime;
        System.out.print(nsPerTime + ",");
    }
    System.out.println();
}

附录4：源代码

import java.io.File;
import java.io.FileNotFoundException;
import java.io.PrintStream;
import java.util.ArrayList;
import java.util.Collections;
import java.util.concurrent.*;

public class MergeSort {
    public static void main(String[] args) {
        File file = new File("MergeSort.txt");
        try {
            System.setOut(new PrintStream(file));
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        }

        int maxNum = 100000;
        int delta = 100;
        int listNum = 10000;
        long lastTime, curTime, nsPerTime;
        Integer[] list;

        System.out.println("BubbleSort");
        for (listNum = delta; listNum <= maxNum; listNum += delta) {
            list = RandomList(listNum);
            lastTime = System.nanoTime();
            BubbleSort(list);
            curTime = System.nanoTime();
            nsPerTime = curTime - lastTime;
            System.out.print(nsPerTime / 1.0E9 + ",");
        }
        System.out.println();

        System.out.println("MergeSort");
        for (listNum = delta; listNum <= maxNum; listNum += delta) {
            list = RandomList(listNum);
            lastTime = System.nanoTime();
            MergeSort(list, 0, list.length - 1);
            curTime = System.nanoTime();
            nsPerTime = curTime - lastTime;
            System.out.print(nsPerTime / 1.0E9 + ",");
        }
        System.out.println();

        System.out.println("MergeSort 3");
        for (listNum = delta; listNum <= maxNum; listNum += delta) {
            list = RandomList(listNum);
            lastTime = System.nanoTime();
            MergeSort2(list, 0, list.length - 1, 3);
            curTime = System.nanoTime();
            nsPerTime = curTime - lastTime;
            System.out.print(nsPerTime / 1.0E9 + ",");
        }
        System.out.println();

        System.out.println("MergeSort 4");
        for (listNum = delta; listNum <= maxNum; listNum += delta) {
            list = RandomList(listNum);
            lastTime = System.nanoTime();
            MergeSort2(list, 0, list.length - 1, 4);
            curTime = System.nanoTime();
            nsPerTime = curTime - lastTime;
            System.out.print(nsPerTime / 1.0E9 + ",");
        }
        System.out.println();

        System.out.println("MergeSort 5");
        for (listNum = delta; listNum <= maxNum; listNum += delta) {
            list = RandomList(listNum);
            lastTime = System.nanoTime();
            MergeSort2(list, 0, list.length - 1, 5);
            curTime = System.nanoTime();
            nsPerTime = curTime - lastTime;
            System.out.print(nsPerTime / 1.0E9 + ",");
        }
        System.out.println();

        System.out.println("MergeSort 6");
        for (listNum = delta; listNum <= maxNum; listNum += delta) {
            list = RandomList(listNum);
            lastTime = System.nanoTime();
            MergeSort2(list, 0, list.length - 1, 6);
            curTime = System.nanoTime();
            nsPerTime = curTime - lastTime;
            System.out.print(nsPerTime / 1.0E9 + ",");
        }
        System.out.println();

        System.out.println("MergeSort Callable");
        for (listNum = delta; listNum <= maxNum; listNum += delta) {
            list = RandomList(listNum);
            ExecutorService threadPool = Executors.newCachedThreadPool();
            MergeSort4 mergeSort4 = new MergeSort4(list, threadPool);
            lastTime = System.nanoTime();
            Future<Boolean> result = threadPool.submit(mergeSort4);
            try {
                result.get();
            } catch (InterruptedException e) {
                e.printStackTrace();
            } catch (ExecutionException e) {
                e.printStackTrace();
            } finally {
                threadPool.shutdown();
            }
            curTime = System.nanoTime();
            nsPerTime = curTime - lastTime;
            System.out.print(nsPerTime + ",");
        }
        System.out.println();

        System.out.println("MergeSort RecursiveTask");
        for (listNum = delta; listNum <= maxNum; listNum += delta) {
            list = RandomList(listNum);
            ForkJoinPool forkJoinPool = new ForkJoinPool();
            MergeSort5 mergeSort5 = new MergeSort5(list);
            lastTime = System.nanoTime();
            Future result = forkJoinPool.submit(mergeSort5);
            try {
                result.get();
            } catch (InterruptedException e) {
                e.printStackTrace();
            } catch (ExecutionException e) {
                e.printStackTrace();
            } finally {
                forkJoinPool.shutdown();
            }
            curTime = System.nanoTime();
            nsPerTime = curTime - lastTime;
            System.out.print(nsPerTime + ",");
        }
        System.out.println();
    }

    public static Integer[] combine(Integer[] a, Integer[] b) {
        ArrayList<Integer> list = new ArrayList<>(
                a.length + b.length);
        int i = 0;
        int j = 0;
        while (i < a.length && j < b.length) {
            if (a[i] < b[j]) {
                list.add(a[i++]);
            } else {
                list.add(b[j++]);
            }
        }
        while (i < a.length) {
            list.add(a[i++]);
        }
        while (j < b.length) {
            list.add(b[j++]);
        }
        return list.toArray(new Integer[a.length + b.length]);
    }

    public static void MergeArray(
            Integer[] list,
            int first,
            int mid,
            int last) {
        int i = first;
        int j = mid + 1;
        int m = mid;
        int n = last;
        ArrayList<Integer> tmp = new ArrayList<>(
                last - first + 1);
        while (i <= m && j <= n) {
            if (list[i] <= list[j]) {
                tmp.add(list[i++]);
            } else {
                tmp.add(list[j++]);
            }
        }
        while (i <= m) {
            tmp.add(list[i++]);
        }
        while (j <= n) {
            tmp.add(list[j++]);
        }
        for (int index = 0; index < tmp.size(); index++) {
            list[first + index] = tmp.get(index);
        }
    }

    public static void MergeSort(
            Integer[] list,
            int first,
            int last) {
        if (first < last) {
            int mid = (first + last) / 2;
            MergeSort(list, first, mid);
            MergeSort(list, mid + 1, last);
            MergeArray(list, first, mid, last);
        }
    }

    public static void MergeSort2(
            Integer[] list,
            int first,
            int last,
            int min) {
        if (last - first > min) {
            int mid = (first + last) / 2;
            MergeSort(list, first, mid);
            MergeSort(list, mid + 1, last);
            MergeArray(list, first, mid, last);
        } else {
            BubbleSort(list, first, last);
        }
    }

    public static void MergeSort3(
            Integer[] list,
            int first,
            int last) {
        if (last - first > 5) {
            int mid = (first + last) / 2;
            MergeSort(list, first, mid);
            MergeSort(list, mid + 1, last);
            MergeArray(list, first, mid, last);
        } else {
            BubbleSort(list, first, last);
        }
    }

    public static class MergeSort4 implements Callable<Boolean> {
        private ExecutorService threadPool;
        private Future<Boolean> loadResult0;
        private Future<Boolean> loadResult1;
        private Integer[] list;
        private int first;
        private int last;
        public MergeSort4(Integer[] list, ExecutorService threadPool) {
            this.list = list;
            this.threadPool = threadPool;
            first = 0;
            last = list.length - 1;
        }
        public MergeSort4(Integer[] list, int first, int last,
                          ExecutorService threadPool) {
            this.list = list;
            this.first = first;
            this.last = last;
            this.threadPool = threadPool;
        }

        /**
         * Computes a result, or throws an exception if unable to do so.
         *
         * @return computed result
         * @throws Exception if unable to compute a result
         */
        @Override
        public Boolean call() throws Exception {
            if (last - first > 5) {
                int mid = (first + last) / 2;
                loadResult0 = threadPool.submit(
                        new MergeSort4(list, first, mid, threadPool)
                );
                loadResult1 = threadPool.submit(
                        new MergeSort4(list, mid + 1, last, threadPool)
                );
                try {
                    if (loadResult0.get() && loadResult1.get()) {
                        MergeArray(list, first, mid, last);
                    }
                } catch (InterruptedException e) {
                    e.printStackTrace();
                } catch (ExecutionException e) {
                    e.printStackTrace();
                }
            } else {
                BubbleSort(list, first, last);
            }
            return true;
        }
    }

    public static class MergeSort5 extends RecursiveTask {
        private Integer[] list;
        private int first;
        private int last;

        public MergeSort5(Integer[] list) {
            this.list = list;
            first = 0;
            last = list.length - 1;
        }

        public MergeSort5(Integer[] list, int first, int last) {
            this.list = list;
            this.first = first;
            this.last = last;
        }

        /**
         * The main computation performed by this task.
         *
         * @return the result of the computation
         */
        @Override
        protected Object compute() {
            if (last - first > 5) {
                int mid = (first + last) / 2;
                MergeSort5 leftTask = new MergeSort5(list, first, mid);
                MergeSort5 rightTask = new MergeSort5(list, mid + 1, last);
                leftTask.fork();
                rightTask.fork();
                leftTask.join();
                rightTask.join();
                MergeArray(list, first, mid, last);
            } else {
                BubbleSort(list, first, last);
            }
            return null;
        }
    }

    public static class CountTask extends RecursiveTask {
        private static final int THRESHOLD = 2;
        private int start;
        private int end;

        public CountTask(int start, int end) {
            this.start = start;
            this.end = end;
        }

        /**
         * The main computation performed by this task.
         *
         * @return the result of the computation
         */
        @Override
        protected Integer compute() {
            int sum = 0;
            boolean canCompute = (end - start) <= THRESHOLD;
            if (canCompute) {
                for (int i = start; i <= end; i++) {
                    sum += i;
                }
            } else {
                int middle = (start + end) / 2;
                CountTask leftTask = new CountTask(start, middle);
                CountTask rightTask = new CountTask(middle + 1, end);
                leftTask.fork();
                rightTask.fork();
                int leftResult = (int) leftTask.join();
                int rightResult = (int) rightTask.join();
                sum = leftResult + rightResult;
            }
            return sum;
        }
    }

    public static Integer[] RandomList(int num) {
        ArrayList<Integer> list = new ArrayList<>(num);
        for (int i = 0; i < num; i++) {
            list.add(i);
        }
        Collections.shuffle(list);
        return list.toArray(new Integer[num]);
    }

    public static void BubbleSort(Integer[] list) {
        for (int i = 0; i < list.length; i++) {
            for (int j = i + 1; j < list.length; j++) {
                if (list[i] > list[j]) {
                    swap(list, i, j);
                }
            }
        }
    }

    public static void BubbleSort(
            Integer[] list,
            int first,
            int last) {
        for (int i = first; i <= last; i++) {
            for (int j = i + 1; j <= last; j++) {
                if (list[i] > list[j]) {
                    swap(list, i, j);
                }
            }
        }
    }

    public static void swap(Integer[] list, int index1, int index2) {
        int tmp = list[index1];
        list[index1] = list[index2];
        list[index2] = tmp;
    }
}

发表评论

CAPTCHAis initialing...

Related Posts