算法练习_归并排序

Posted on | Edited on | Comments: | Views:
归并排序的学习笔记以及代码实现

概念

问题描述

给定无序数组，将数组按从小到大的顺序排列。

算法思想

归并排序可以分为：

  • 自底向上的归并：从最小规模的数组开始归并，然后成对归并已经排序好的小规模数组，直到将整个数组归并。

    iyoqeK.md.png

  • 自顶向下的归并：将数组切分为小规模数组，再分别对小规模数组排序，最后进行归并。

    iyoIzR.md.png

图解

此为自底向上的归并排序

代码实现

自底向上的归并排序

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
/**
 * @author zhyee
 * @date 2018/10/23 上午11:45
 */
public class MergeSortBU {

    public int[] mergeSort(int[] a) {
        /* */
        return this.mergeSort(a, /*base*/ 2);
    }

    public int[] mergeSort(int[] a, int size) {
        int cycles = a.length % size == 0 ? a.length / size : a.length / size + 1;
        if (cycles == 1) {
            merge(a, 0, size);
            return a;
        }
        for (int i = 0; i <= cycles; i = i + size) {
            merge(a, i, size);
        }
        size = size + size;
        return mergeSort(a, size);
    }

    private int[] merge(int[] a, int lo, int size) {
        int hi = Math.min(lo + size - 1, a.length - 1);
        int sortSize = hi - lo + 1;
        int[] aux = new int[sortSize];
        int leftLow = lo;
        int mid = lo + size / 2;
        int rightLow = lo + size / 2;
        int i = 0;

        while (true) {
            if (leftLow < mid && rightLow <= hi) {
                if (a[leftLow] > a[rightLow]) {
                    aux[i] = a[rightLow];
                    rightLow++;
                } else {
                    aux[i] = a[leftLow];
                    leftLow++;
                }
                i++;
            } else if (leftLow < mid) {
                aux[i] = a[leftLow];
                i++;
                leftLow++;
            } else if (rightLow <= hi) {
                aux[i] = a[rightLow];
                i++;
                rightLow++;
            } else {
                break;
            }
        }
        System.arraycopy(aux, 0, a, lo, sortSize);
        return a;
    }
}

自底向上的归并排序

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
/**
 * @author zhyee
 * @date 2018/10/22 下午4:37
 */
public class MergeSortUD {

    public int[] mergeSort(int[] a, int lo, int hi) {
        int size = hi - lo + 1;
        int mid = lo + (size % 2 == 0 ? (size / 2) - 1 : (size / 2));

        int leftLow = lo;
        int rightLow = mid + 1;

        if (size > 2) {
            mergeSort(a, leftLow, mid);
            mergeSort(a, rightLow, hi);
        }

        // sorted two parts [lo .. mid]  [mid+1, hi]
        int[] temp = new int[size];
        int i = 0;

        while (true) {
            if (leftLow <= mid && rightLow <= hi) {
                if (a[leftLow] > a[rightLow]) {
                    temp[i] = a[rightLow];
                    rightLow++;
                    i++;
                } else {
                    temp[i] = a[leftLow];
                    leftLow++;
                    i++;
                }
            } else if (leftLow <= mid) {
                temp[i] = a[leftLow];
                i++;
                leftLow++;
            } else if (rightLow <= hi) {
                temp[i] = a[rightLow];
                i++;
                rightLow++;
            } else {
                //end
                break;
            }
        }
        System.arraycopy(temp, 0, a, lo, size);
        return a;
    }
}

特点

归并排序的时间复杂度可以缩短到 NlogN，但是它所需要的额外空间和 N 成正比。

参考文档

《算法》