ForkJoin和冒泡排序组合实现的归并排序

阳光穿透心脏的1/2处 2022-11-21 15:00 42阅读 0赞

package com.example.demo.studyThread.day4;
    
    import com.example.demo.studyThread.day3.MarkArray;
    import com.example.demo.studyThread.day3.SumArray;
    
    import java.util.Random;
    import java.util.concurrent.ForkJoinPool;
    import java.util.concurrent.RecursiveTask;
    
    public class BubbleSort {
    
        private static int MAX = 100;
        private static int[] meiemi = new int[MAX];
    
        static {
            Random random = new Random();
            for (int i = 1; i <= MAX; i++) {
                meiemi[i - 1] = random.nextInt(MAX);
            }
        }
    
        //冒泡排序
        //如果是升序排列的话，每一轮排序找出最大，下一轮都少比较一次
        private static int[] bubbleSort(int[] src){
            for (int i = 0; i < src.length-1; i++) {
                for (int j = 0; j < src.length-i-1; j++) {
                    int min;
                    if (src[j]>src[j+1]){
                        min = src[j];
                        src[j] = src[j+1];
                        src[j+1]=min;
                    }
                }
            }
            return src;
        }
    
        /**
         * 功能描述 : 将两个有序数组合并起来  一次循环确认新数组的一个最小值，放进角标为i的位置
         *
         * @param arr1 数组1
         * @param arr2 数组2
         * @return {@link int[]}
         * @author Ziyear 2020-5-21 20:12
         */
        private static int[]  joinInts(int[] arr1, int[] arr2) {
            int left = 0;
            int right = 0;
            int[] mergeArr = new int[arr1.length + arr2.length];
            if (mergeArr.length == 0) {
                return null;
            }
            for (int i = 0; i < arr1.length + arr2.length; i++) {
                if (arr1.length == left) {
                    mergeArr[i] = arr2[right];
                    right++;
                    continue;
                } else if (arr2.length == right) {
                    mergeArr[i] = arr1[left];
                    left++;
                    continue;
                }
                if (arr1[left] <= arr2[right]) {
                    mergeArr[i] = arr1[left];
                    left++;
                } else {
                    mergeArr[i] = arr2[right];
                    right++;
                }
            }
            return mergeArr;
        }
    
        //用forkjoin实现归并排序
        private static class MergeSortByFoinJoin extends RecursiveTask<int[]>{
            private final static int THRESHOLD = 20;
            private int[] src;
            private int fromIndex;
            private  int toIndex;
    
            public MergeSortByFoinJoin(int[] src, int fromIndex, int toIndex) {
                this.src = src;
                this.fromIndex = fromIndex;
                this.toIndex = toIndex;
            }
    
            @Override
            protected int[] compute() {
                if (toIndex-fromIndex<=THRESHOLD){
                    return bubbleSort(src);
                }else{
                    int mid = (fromIndex+toIndex)/2;
                    MergeSortByFoinJoin left = new MergeSortByFoinJoin(src,fromIndex,mid);
                    MergeSortByFoinJoin right = new MergeSortByFoinJoin(src,mid+1,toIndex);
                    invokeAll(left,right);
                    int[] leftjoin = left.join();
                    return leftjoin;
    
                }
            }
        }
    
    
        public static void main(String[] args) {
           StringBuilder string = new StringBuilder();
            int[] s = {88,3,73,65,99,108,16,14,19,77,65,98,90,11,80,43};
            for (int i:meiemi
                 ) {
                string.append(i+",");
            }
            System.out.println(string);
            System.out.println(
                    meiemi.length
            );
            StringBuilder sorts = new StringBuilder();
            ForkJoinPool pool = new ForkJoinPool();
            MergeSortByFoinJoin foinJoin = new MergeSortByFoinJoin(meiemi,0,meiemi.length-1);
            pool.invoke(foinJoin);
            int[] join = foinJoin.join();
            for (int i:join
            ) {
                sorts.append(i+",");
            }
            System.out.println(sorts+"length:"+join.length);
        }
    }