算法-归并排序

发表于 更新于

归并排序利用分而治之的办法将问题大化小，平均、最坏、最好时间复杂度都是O(nlogn)，采用递归法：

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

递归法的Java实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
package com;

/**
 *
 */
import java.util.Arrays;
import java.util.Random;

/**
 */
public class MergeSort {
    private static int MAX = 100000;//100000个数进行排序
    private static int[] ints = new int[MAX];
    static {
        Random r = new Random();
        for(int index = 1 ; index <= MAX ; index++) {
            ints[index - 1] = r.nextInt(10000000);
        }
    }


    public static void main(String []args){
        long start = System.currentTimeMillis ();
        //ints = new int[]{9,8,7,6,5,4,3,2,1};
        sort( ints );
        System.out.println(Arrays.toString( ints ));
        System.out.println ( (System.currentTimeMillis () - start) );
    }

    public static void sort(int []arr){
        sort(arr,0,arr.length-1);
    }

    /**
     * 以待排序数组 arr {9,8,7,6,5,4,3,2,1}举例：程序的运行流程如下: (如下数字表示数组下标)
     *  1.  sort 0, 8
     *  2.  sort 0, 4 (left, mid)
     *  3.  sort 0, 2 (left, mid)
     *  4.  sort 0, 1 (left, mid)
     *  5.  sort 0, 0 (left, mid) (自然有序，直接返回)
     *  6.  sort 1, 1 (mid+1, right) (自然有序，直接返回)
     *  7. merge [0,0,1] (合并[0],[1]成[0,1])
     *  9. 递归返回到 3. sort 0, 2 的下一步: sort 2, 2 (mid+1, right) (自然有序，直接返回)
     * 10. merge [0,1,2] (合并[0,1],[2]成[0,2])
     * 11. 递归返回到 2. sort 0, 4 的下一步: sort3, 4 (mid+1, right)
     * 12. sort 3, 3 (left, mid) (自然有序，直接返回)
     * 13. sort 4, 4 (mid+1, right) (自然有序，直接返回)
     * 15. merge [3,3,4] (合并[3],[4]成[3,4])
     * 16. merge [0,2,4] (合并[0,2],[3,4]成[0,4]) （至此，左边排序sort(arr,left,mid)完成）
     * 17. sort 5, 8 (mid+1, right) (继续进行右边排序sort(arr,mid+1,right))
     * 18. sort 5, 6 (left, mid)
     * 19. sort 5, 5 (left, mid) (自然有序，直接返回)
     * 20. sort 6, 6 (mid+1, right) (自然有序，直接返回)
     * 21. merge [5,5,6] (合并[5],[6]成[5,6])
     * 22. 递归返回到 17. sort 5, 8 的下一步: sort 7, 8 (mid+1, right)
     * 23. sort 7, 7 (left, mid) (自然有序，直接返回)
     * 24. sort 8, 8 (mid+1, right) (自然有序，直接返回)
     * 25. merge [7,7,8] (合并[7],[8]成[7,8])
     * 26. merge [5,6,8] (合并[5,6],[7,8]成[5,8]) (至此，右边排序sort(arr,mid+1,right)完成)
     * 27. merge [0,4,8] (合并[0,4],[5,8]成[0,8]) (至此，左右两边合并排序完成)
     * @param arr
     * @param left
     * @param right
     */
    private static void sort(int[] arr,int left,int right){
        if(left<right){
            int mid = (left+right)/2;
            sort(arr,left,mid);//左边归并排序，使得左子序列有序
            sort(arr,mid+1,right);//右边归并排序，使得右子序列有序
            merge(arr,left,mid,right);//将两个有序子数组合并操作
        } else {
            return;
        }
    }

    private static void merge(int[] arr,int left,int mid,int right){
        int i = left;//左序列指针
        int j = mid+1;//右序列指针
        int t = 0;//临时数组指针
        int[] temp = new int[arr.length];
        while (i<=mid && j<=right){
            if(arr[i]<=arr[j]){
                temp[t++] = arr[i++];
            }else {
                temp[t++] = arr[j++];
            }
        }
        while(i<=mid){//将左边剩余元素填充进temp中
            temp[t++] = arr[i++];
        }
        while(j<=right){//将右序列剩余元素填充进temp中
            temp[t++] = arr[j++];
        }
        t = 0;
        //将temp中的元素全部拷贝到原数组中
        while(left <= right){
            arr[left++] = temp[t++];
        }
    }
}

由以上递归法的实现可知：大化小排序是可以并发进行的，利用多线程并发排序如下：ForkJoinTask任务排序：

ForkJoinSortTask.java:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
package com;

import java.util.Arrays;
import java.util.concurrent.RecursiveTask;

/**
 *
 */
public class ForkJoinSortTask extends RecursiveTask<int[]> {
    private int[] ints;

    ForkJoinSortTask(int[] ints) {
        this.ints = ints;
    }

    /**
     * 归并排序的特征：利用分治法，可以利用多线程同时进行
     * @return
     */
    @Override
    protected int[] compute() {
        int len = ints.length;
        if (len > 2) {
            int mid = len / 2;
            ForkJoinSortTask leftTask = new ForkJoinSortTask ( Arrays.copyOf ( ints, mid) );
            leftTask.fork ();
            ForkJoinSortTask rightTask = new ForkJoinSortTask ( Arrays.copyOfRange ( ints, mid, len) );
            rightTask.fork ();
            return merge(leftTask.join (), rightTask.join ());
        } else {
            if (len != 1 && ints[0] >= ints[1]) {
                int tmp = ints[1];
                ints[1] = ints[0];
                ints[0] = tmp;
            }
            return ints;
        }
    }

    /**
     * 将两个有序的数组合并成一个有序数组
     */
    private int[] merge(int[] leftSorted, int[] rightSorted) {
        int left = 0;
        int right = 0;
        int[] merged = new int[leftSorted.length + rightSorted.length];
        for (int i = 0; i < leftSorted.length + rightSorted.length; i++) {
            if (left == leftSorted.length) {
                merged[i] = rightSorted[right];
                right++;
                continue;
            } else if (right == rightSorted.length) {
                merged[i] = leftSorted[left];
                left++;
                continue;
            }
            if (leftSorted[left] < rightSorted[right]) {
                merged[i] = leftSorted[left];
                left++;
            } else {
                merged[i] = rightSorted[right];
                right++;
            }
        }
        return merged;
    }

}

ForkJoinSort.java：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
package com;

import java.util.Arrays;
import java.util.Random;
import java.util.concurrent.ExecutionException;
import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.ForkJoinTask;

/**
 *
 */
public class ForkJoinSort {
    private static int MAX = 100000;//100000个数进行排序
    private static int[] ints = new int[MAX];
    static {
        Random r = new Random();
        for(int index = 1 ; index <= MAX ; index++) {
            ints[index - 1] = r.nextInt(10000000);
        }
    }

    public static void main(String[] args) throws ExecutionException, InterruptedException {
        long start = System.currentTimeMillis ();
        ForkJoinPool forkJoinPool = new ForkJoinPool (  );
        ForkJoinSortTask forkJoinSortTask = new ForkJoinSortTask ( ints );
        //ForkJoinSortTask forkJoinSortTask = new ForkJoinSortTask ( new int[]{9,8,7,6,5,4,3,2,1});
        ForkJoinTask<int[]> forkJoinTask = forkJoinPool.submit ( forkJoinSortTask );
        int[] result = forkJoinTask.get ();
        System.out.println( Arrays.toString(result));
        System.out.println ( (System.currentTimeMillis () - start) );
    }
}

对比以上两种排序实现，未使用多线程，排序100000个随机数大概需要5秒，利用多线程只需要200毫秒以内

-------------本文结束感谢您的阅读-------------
Good for you!