归并排序算法

 1 public static void main(String[] args) {
 2         int arr[] = {2,7,1,5,9,6,10}; //要排序的数组
 3         int temp[] = new int[arr.length]; //中间数组
 4         mergeSort(arr,0,arr.length-1,temp);
 5         System.out.println(Arrays.toString(arr));
 6     }
 7 
 8     //分解加合并方法，即归并排序
 9     public static void mergeSort(int arr[], int left,int right, int temp[]) {
10         if (left >= right) {
11             return;
12         }
13         if (left < right) {
14             int mid = (left + right)/2; //以中间索引进行分解
15             //分离左边序列
16             mergeSort(arr, left, mid, temp);
17             //分离右边序列
18             mergeSort(arr, mid+1, right, temp);
19             //合并
20             merge(arr, left, mid, right, temp);
21         }
22     }
23 
24     //合并
25     public static void merge(int arr[], int left, int mid, int right, int temp[]) {
26         int i = left;//左边有序序列初始索引
27         int j = mid+1;//右边有序序列初始索引
28         int t = 0; //temp 初始索引
29 
30         //先把左右两边有序的数据按规则填充到temp数组中
31         //直到左右两边有序序列有一边不能处理为止
32         while ( i<=mid && j<=right) {
33             //比较左边和右边的数据，小的那方先存入temp
34             if ( arr[i] <= arr[j]) {
35                 temp[t] = arr[i];
36                 t += 1;
37                 i += 1;
38             } else {
39                 temp[t] = arr[j];
40                 t += 1;
41                 j += 1;
42             }
43         }
44         //如果有一边有剩余数据则依次填入temp数组中
45         while ( i<=mid){
46             temp[t] = arr[i];
47             t += 1;
48             i += 1;
49         }
50         while ( j<=right ) {
51             temp[t] = arr[j];
52             t += 1;
53             j += 1;
54         }
55         //将temp数组拷贝到arr中
56         //并不是一次性合并完后拷贝进数组
57         t = 0;
58         int tempLeft = left; //左边要合并序列的索引
59         System.out.println("tl="+tempLeft + "right"+right);
60         while(tempLeft<=right) {
61             arr[tempLeft] = temp[t];
62             t += 1;
63             tempLeft += 1;
64         }
65 }

public static void main (String[] args) throws InterruptedException {
        int[] arr = {2,7,1,5,9,6,10,50,20,30,66,11,45,111};
        System.out.println(Arrays.toString(arr));
        int[] temp = new int[arr.length];
        //Fork/Join 从这里开始
        ForkJoinPool forkJoinPool = new ForkJoinPool();
        ll.mergeTask task = new ll.mergeTask(arr, temp, 0, arr.length-1);//创建任务
        forkJoinPool.execute(task);//执行任务
        forkJoinPool.awaitTermination(2, TimeUnit.SECONDS);//阻塞当前线程直到pool中的任务都完成了
        System.out.println(Arrays.toString(arr));
    }

    //递归
    private static void mergeSort(int[] nums,int[] tmp,int left,int right){
        if(left<right){
            int center = (left+right)/2;
            mergeSort(nums,tmp,left,center);
            mergeSort(nums,tmp,center+1,right);
            merge(nums,tmp,left,center+1,right);
        }
    }

    //合并
    private static void merge(int[] nums,int[] tmp,int leftPos, int rightPos, int rightEnd){
        int leftEnd = rightPos-1;
        int tmpPos = leftPos;
        int numElements = rightEnd - leftPos + 1;

        while(leftPos<=leftEnd&&rightPos<=rightEnd){
            if(nums[leftPos]<nums[rightPos])
                tmp[tmpPos++]=nums[leftPos++];
            else
                tmp[tmpPos++]=nums[rightPos++];
        }
        while(leftPos<=leftEnd)
            tmp[tmpPos++]=nums[leftPos++];

        while(rightPos<=rightEnd)
            tmp[tmpPos++]=nums[rightPos++];

        for(int i = 0;i<numElements;i++,rightEnd--)
            nums[rightEnd]=tmp[rightEnd];
    }
    public static void mergeSort(int[] nums){
        int[] tmp = new int[nums.length];
        mergeSort(nums,tmp,0,nums.length-1);
    }

    static class mergeTask extends RecursiveAction {
        private static final int THRESHOLD = 2;//设置任务大小阈值
        private int start;
        private int end;
        private int[] data;
        private int[] tmp;

        public mergeTask(int[] data, int[] tmp, int start, int end){
            this.data = data;
            this.tmp = tmp;
            this.start = start;
            this.end = end;
        }

        @Override
        protected void compute(){
            if((end - start)<=THRESHOLD){
                mergeSort(data,tmp,start,end);
            }else{
                int center = (start + end)/2;
                ll.mergeTask leftTask = new ll.mergeTask(data, tmp, start, center);
                ll.mergeTask rightTask = new ll.mergeTask(data, tmp, center+1, end);

                leftTask.fork();
                rightTask.fork();

                leftTask.join();
                rightTask.join();

                merge(data, tmp, start, center+1, end);

            }
        }
    }