关于土豆哥
一只文艺型码农
归并排序及其Java并发实现
归并排序及其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;
    }
}
赞赏
本文原作者为Mortal,原文首发于作者CSDN博客。Mortal现已加入本站,本文为Mortal直接发布,如需转载请通过作者CSDN博客或本站联系表单申请授权。

发表评论

textsms
account_circle
email

CAPTCHAis initialing...

归并排序及其Java并发实现
冒泡排序 因为在归并排序的简化过程中需要用到冒泡排序,所以这里先做一下简单介绍。 冒泡排序(Bubble Sort),是一种计算机科学领域的较简单的排序算法。 它重复地走访过要排序的…
扫描二维码继续阅读
2018-05-15