java归并排序,单线程vs多线程

摘要:
对于需要排序的数组A[0..N-1],将其合并并排序为两部分:A[0..N/2-1]和A[N/2..N-1]并递归排序每个子数组,然后将两个排序的子数组合并为有序数组。

一、什么是归并排序

归并排序又称合并排序,它是成功应用分治技术的一个完美例子。对于一个需要排序的数组A[0..n-1],归并排序把它一分为二:A[0..n/2-1]和A[n/2..n-1],并对每个子数组递归排序,然后把这两个排好序的子数组合并为一个有序数组。下面是归并排序的例子图解:java归并排序,单线程vs多线程第1张

二、单线程实现归并排序

package com.bob.algorithms.sort;

import java.util.Arrays;

import com.bob.algorithms.SortStrategy;

/**
 * 归并排序
 * 
 * @author bob
 *
 */
public class SingleThreadMergeSort implements SortStrategy {

    public int[] sort(int[] rawArray) {
        mergeSort(rawArray);
        return rawArray;
    }

    /**
     * 分解并合并排序,升序
     * 
     * @param intArr
     */
    private void mergeSort(int[] intArr) {
        if (intArr.length > 1) {
            // 如果数组长度大于1就分解称两份
            int[] leftArray = Arrays.copyOfRange(intArr, 0, intArr.length / 2);
            int[] rightArray = Arrays.copyOfRange(intArr, intArr.length / 2, intArr.length);
            mergeSort(leftArray);
            mergeSort(rightArray);

            // 合并且排序
            merge(leftArray, rightArray, intArr);
        }
    }

    /**
     * 合并排序
     * 
     * @param leftArray
     * @param rightArray
     * @param intArr
     */
    private void merge(int[] leftArray, int[] rightArray, int[] intArr) {

        // i:leftArray数组索引,j:rightArray数组索引,k:intArr数组索引
        int i = 0, j = 0, k = 0;
        while (i < leftArray.length && j < rightArray.length) {
            // 当两个数组中都有值的时候,比较当前元素进行选择
            if (leftArray[i] < rightArray[j]) {
                intArr[k] = leftArray[i];
                i++;
            } else {
                intArr[k] = rightArray[j];
                j++;
            }
            k++;
        }

        // 将还剩余元素没有遍历完的数组直接追加到intArr后面
        if (i == leftArray.length) {
            for (; j < rightArray.length; j++, k++) {
                intArr[k] = rightArray[j];
            }
        } else {
            for (; i < leftArray.length; i++, k++) {
                intArr[k] = leftArray[i];
            }
        }
    }
}

三、使用Fork/Join框架实现归并排序

Fork/Join是从JDK 1.7 加入的并发计算框架。

package com.bob.algorithms.sort;

import java.util.Arrays;
import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.RecursiveAction;

import com.bob.algorithms.SortStrategy;

public class ForkJoinMergeSort implements SortStrategy {

    public int[] sort(int[] rawArray) {
        ForkJoinPool pool = new ForkJoinPool();
        pool.invoke(new MergeSort(rawArray));
        return rawArray;
    }

    /**
     * 使用Fork/join的方式进行归并排序,充分利用cpu
     * 
     * @author zhangwensha
     *
     */
    private static class MergeSort extends RecursiveAction {

        private static final long serialVersionUID = 425572392953885545L;
        private int[] intArr;

        public MergeSort(int[] intArr) {
            this.intArr = intArr;
        }

        @Override
        protected void compute() {
            if (intArr.length > 1) {
                // 如果数组长度大于1就分解称两份
                int[] leftArray = Arrays.copyOfRange(intArr, 0, intArr.length / 2);
                int[] rightArray = Arrays.copyOfRange(intArr, intArr.length / 2, intArr.length);

                // 这里分成两份执行
                invokeAll(new MergeSort(leftArray), new MergeSort(rightArray));

                // 合并且排序
                merge(leftArray, rightArray, intArr);
            }
        }

        /**
         * 合并排序
         * 
         * @param leftArray
         * @param rightArray
         * @param intArr
         */
        private void merge(int[] leftArray, int[] rightArray, int[] intArr) {

            // i:leftArray数组索引,j:rightArray数组索引,k:intArr数组索引
            int i = 0, j = 0, k = 0;
            while (i < leftArray.length && j < rightArray.length) {
                // 当两个数组中都有值的时候,比较当前元素进行选择
                if (leftArray[i] < rightArray[j]) {
                    intArr[k] = leftArray[i];
                    i++;
                } else {
                    intArr[k] = rightArray[j];
                    j++;
                }
                k++;
            }

            // 将还剩余元素没有遍历完的数组直接追加到intArr后面
            if (i == leftArray.length) {
                for (; j < rightArray.length; j++, k++) {
                    intArr[k] = rightArray[j];
                }
            } else {
                for (; i < leftArray.length; i++, k++) {
                    intArr[k] = leftArray[i];
                }
            }
        }

    }
}
 

四、单线程 pk 多线程

编写了舞台类,通过调整generateIntArray(10000000)的输入参数来设置待排序数组长度,试验中没有对堆容量进行设置。

package com.bob.algorithms;

import java.util.Arrays;
import java.util.Date;

import com.bob.algorithms.common.CommonUtil;
import com.bob.algorithms.sort.ForkJoinMergeSort;
import com.bob.algorithms.sort.SingleThreadMergeSort;

/**
 * 舞台类,专门用来测试算法的时间
 * 
 * @author bob
 *
 */
public class Stage {

    public static void main(String[] args) {

        // 变量定义
        long begintime = 0;
        long endtime = 0;

        // 生成排序数据
        int[] rawArr = generateIntArray(10000000);
        int[] rawArr2 = Arrays.copyOf(rawArr, rawArr.length);

        begintime = new Date().getTime();
        new SingleThreadMergeSort().sort(rawArr);
        //System.out.println(Arrays.toString(new SingleThreadMergeSort().sort(rawArr)));
        endtime = new Date().getTime();
        System.out.println("单线程归并排序花费时间:" + (endtime - begintime));
        System.out.println("是否升序:"+CommonUtil.isSorted(rawArr, true));

        begintime = new Date().getTime();
        new ForkJoinMergeSort().sort(rawArr2);
        //System.out.println(Arrays.toString(new ForkJoinMergeSort().sort(rawArr2)));
        endtime = new Date().getTime();
        System.out.println("Fork/Join归并排序花费时间:" + (endtime - begintime));
        System.out.println("是否升序:"+CommonUtil.isSorted(rawArr2, true));
    }

    /**
     * 生成int类型的数组
     * 
     * @return
     */
    private static int[] generateIntArray(int length) {
        int[] intArr = new int[length];
        for (int i = 0; i < length; i++) {
            intArr[i] = new Double(Math.random() * length).intValue();
        }
        return intArr;
    }
}
 

以下是数组容量在各个量级时,两种方法效率对比:

数组长度100100010000100000100000010000000
单线程 (ms)127331882139
Fork/Join (ms)8917633581133

通过统计可以发现,当待排序序列长度较小时,使用单线程效率要高于多线程,但是随着数量不断增加,多线程执行时间越来越接近单线程的执行时间,最终在1000万这个量级开始速率远超单线程。工作中不能滥用多线程,在该使用的时候使用可以加快效率,充分利用多核。但是在不该用的时候使用徒增工作量,有可能效率还不如单线程。 感兴趣的朋友可以通过下面代码地址找到运行的全部源码自己跑跑试试看。

五、本文代码地址

包括本篇在内以后所有代码统一存放地址为: 
https://github.com/mingbozhang/algorithm

六、参考 

https://docs.oracle.com/javase/tutorial/essential/concurrency/forkjoin.html 
《算法设计与分析基础(第3版)》

免责声明:文章转载自《java归并排序,单线程vs多线程》仅用于学习参考。如对内容有疑问,请及时联系本站处理。

上篇设计模式演练——抽象工厂模式Maven将依赖的所有jar包打成一个jar下篇

宿迁高防,2C2G15M,22元/月;香港BGP,2C5G5M,25元/月 雨云优惠码:MjYwNzM=

相关文章

java多线程快速入门(五)

常用线程api方法 多线程运行状态 1、新建状态 用new创建一个线程 2、就绪状态 当调用线程的start()方法 3、运行状态 当线程获得cpu,开始执行run方法 4、阻塞状态 线程通过调用sleep方法进入睡眠状态 线程试图得到一个锁,而该锁正被其它线程持有 线程在等待某个触发条件 5、死亡状态 run方法正常退出而自然死亡 一个未捕获的异常终...

有关JAVA多线程的理解

不同于c++等语言的调用操作系统的线程调控机制来实现多线程,java语言内置了多线程的api包,因此可以更加方便的使用多线程技术。(1)线程的问题。进程是程序的一次动态执行过程,它对应了从代码加载、执行至执行完毕的一个完整过程,这个过程也是进程本身从产生、发展至消亡的过程。线程是比进程更小的单位,一个进程执行过程中可以产生多个线程,每个线程有自身的产生、存在...

QT多线程中使用QTcpSocket遇到的读写数据问题

多线程中使用QTcpSocket在run()方法中new QTcpSocket;然后监听readyRead()信号connect(m_pTcpSocket,SIGNAL(readyRead()),this,SLOT(sloat_RecvData())); 问题是当需要给服务器发送一段命令时(使用m_pTcpSocket->write(byteArra...

多线程的并发控制(synchronized与ThreadLocal)

synchronized synchronized的4种用法: 1.方法声明时使用,线程获得的是成员锁. 2.对某一代码块使用,synchronized后跟括号,括号里是变量,线程获得的是成员锁. 3.synchronized后面括号里是一对象,此时,线程获得的是对象锁. 4.synchronized后面括号里是类,此时,线程获得的是对象锁. ThreadL...

线程与进程(二)

1.线程与进程的基本概念: 进程:每个进程都有独立的代码和数据空间(进程上下文),进程间的切换会有较大的开销,一个进程包含1--n个线程。(进程是资源分配的最小单位) 线程:同一类线程共享代码和数据空间,每个线程有独立的运行栈和程序计数器(PC),线程切换开销小。(线程是cpu调度的最小单位) 多进程是指操作系统能同时运行多个任务(程序)。 多线程是指在同一...

go 快速排序 归并排序

快速排序 package main import "fmt" func main() { a := []int{3,12,3,5,12,3,123,1,5,0} QuickSort(a, 0, len(a) - 1) fmt.Println("a: ", a) } func QuickSort(nums []int,begin,...