排序算法--归并排序(MergeSort)原理、适用场景及代码示例_merge sort

归并排序

归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)。

它将输入数组分成两半，为这两半调用自己，然后合并已排序的两半。
merge函数的作用是合并两个部分。合并merge(arr, l, m, r)是一个关键过程，它假设arr[l…m] 和 arr[m+1…r] 已经排好序，并将两个已排序的子数组合并为一个。

归并排序是稳定排序，它也是一种十分高效的排序，能利用完全二叉树特性的排序一般性能都不会太差。
java中Arrays.sort()采用了一种名为TimSort的排序算法，就是归并排序的优化版本。

从下面的排序过程图例中可看出，每次合并操作的平均时间复杂度为O(n)，而完全二叉树的深度为|log2n|。总的平均时间复杂度为O(nlogn)。而且，归并排序的最好，最坏，平均时间复杂度均为O(nlogn)。
详见：merge-sort

分治【 Divide and Conquer 】策略

Divide : 将问题划分为更小的子问题。
Conquer: 通过递归调用来解决子问题，直到解决为止。
combine 或 merge: 将子问题组合起来，得到整个问题的最终解。

实现思路

MergeSort(arr[], l,  r)
If r > l
     1. Find the middle point to divide the array into two halves:  
             middle m = l+ (r-l)/2
     2. Call mergeSort for first half:   
             Call mergeSort(arr, l, m)
     3. Call mergeSort for second half:
             Call mergeSort(arr, m+1, r)
     4. Merge the two halves sorted in step 2 and 3:
             Call merge(arr, l, m, r)
             
1
2
3
4
5
6
7
8
9
10
11

排序过程图例

下面来自维基百科的图显示了一个示例数组{38,27,43,3,9,82,10}的完整归并排序过程。
如果仔细看一下图表，可以看到数组被递归地分成两半，直到大小变为1。一旦大小变为1，合并进程就开始行动，并开始合并数组，直到合并完整的数组。

缺点及适用场景

缺点

• 对于较小的任务，比其他排序算法更慢。
• 归并排序算法需要一个额外的内存空间0(n)为临时数组。
• 即使数组是有序的，它也会贯穿整个过程。

适用场景

• 适用于链表排序，可以在O(nLogn)时间内排序。通常是链表排序的首选
• 计算
• 用于外部排序(External Sorting)

源码示例

归并排序示例

public class MergeSort {
    // Merges two subarrays of arr[].
    // First subarray is arr[l..m] Second subarray is arr[m+1..r]
    void merge(int arr[], int l, int m, int r) {
        // Find sizes of two subarrays to be merged
        int n1 = m - l + 1;
        int n2 = r - m;

        /* Create temp arrays */
        int L[] = new int[n1];
        int R[] = new int[n2];

        /*Copy data to temp arrays*/
        for (int i = 0; i < n1; ++i) {
            L[i] = arr[l + i];
        }
        for (int j = 0; j < n2; ++j) {
            R[j] = arr[m + 1 + j];
        }
        /* Merge the temp arrays */

        // Initial indexes of first and second subarrays
        int i = 0, j = 0;

        // Initial index of merged subarray array
        int k = l;
        while (i < n1 && j < n2) {
            if (L[i] <= R[j]) {
                arr[k] = L[i];
                i++;
            } else {
                arr[k] = R[j];
                j++;
            }
            k++;
        }

        /* Copy remaining elements of L[] if any */
        while (i < n1) {
            arr[k] = L[i];
            i++;
            k++;
        }

        /* Copy remaining elements of R[] if any */
        while (j < n2) {
            arr[k] = R[j];
            j++;
            k++;
        }
    }

    // Main function that sorts arr[l..r] using merge()
    void sort(int arr[], int l, int r) {
        if (l < r) {
            // Find the middle point
            int m = l + (r - l) / 2;

            // Sort first and second halves
            sort(arr, l, m);
            sort(arr, m + 1, r);

            // Merge the sorted halves
            merge(arr, l, m, r);
        }
    }

    /* A utility function to print array of size n */
    static void printArray(int arr[]){
        int n = arr.length;
        for (int i = 0; i < n; ++i) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

    // Driver code
    public static void main(String args[]) {
        int arr[] = { 38, 27, 43, 3, 9, 82, 10 };

        System.out.println("Given Array");
        printArray(arr);

        MergeSort ob = new MergeSort();
        ob.sort(arr, 0, arr.length - 1);

        System.out.println("\nSorted array");
        printArray(arr);
    }
}

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

链表排序

通常是链表排序的首选。链表缓慢的随机访问性能使得其他一些算法(如快速排序)的性能很差，而其他算法(如堆排序)则完全不可能。

public class linkedList {
    static class Node {
        int data;
        Node next;
        Node(int key) {
            this.data = key;
            next = null;
        }
    }
    // Function to merge sort
    static Node mergeSort(Node head) {
        if (head.next == null) {
            return head;
        }
        Node mid = findMid(head);
        Node head2 = mid.next;
        mid.next = null;
        Node newHead1 = mergeSort(head);
        Node newHead2 = mergeSort(head2);
        Node finalHead = merge(newHead1, newHead2);

        return finalHead;
    }

    // Function to merge two linked lists
    static Node merge(Node head1, Node head2)
    {
        Node merged = new Node(-1);
        Node temp = merged;

        // While head1 is not null and head2 is not null
        while (head1 != null && head2 != null) {
            if (head1.data < head2.data) {
                temp.next = head1;
                head1 = head1.next;
            }
            else {
                temp.next = head2;
                head2 = head2.next;
            }
            temp = temp.next;
        }

        // While head1 is not null
        while (head1 != null) {
            temp.next = head1;
            head1 = head1.next;
            temp = temp.next;
        }

        // While head2 is not null
        while (head2 != null) {
            temp.next = head2;
            head2 = head2.next;
            temp = temp.next;
        }
        //删除-1的临时节点
        return merged.next;
    }

    // 基于龟兔赛跑寻找中点
    static Node findMid(Node head) {
        Node slow = head, fast = head.next;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    // Function to print list
    static void printList(Node head)
    {
        while (head != null) {
            System.out.print(head.data + " ");
            head = head.next;
        }
    }

    // Driver Code
    public static void main(String[] args)
    {
        Node head = new Node(7);
        Node temp = head;
        temp.next = new Node(10);
        temp = temp.next;
        temp.next = new Node(5);
        temp = temp.next;
        temp.next = new Node(20);
        temp = temp.next;
        temp.next = new Node(3);
        temp = temp.next;
        temp.next = new Node(2);

        // Apply merge Sort
        head = mergeSort(head);
        System.out.print("\nSorted Linked List is: \n");
        printList(head);
    }
}

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
101

数组的逆序计数

数组的逆序计数表示how far (or close) the array is from being sorted。
如果数组已经排序，则逆序计数为0，但如果数组按反顺序排序，则逆序计数为最大。
如数组 arr[] = {8, 4, 2, 1}，有如下6个逆序
Explanation: Given array has six inversions:
(8, 4),(8, 2), (8, 1), (4, 2), (4, 1), (2, 1).

public class MergeSort {
    // Driver code
    public static void main(String args[]) {
        int[] arr = { 1, 20, 6, 4, 5,2,3,1,8,2 };

        System.out.println(getInvCount(arr));
        int[] arr1 = { 1, 20, 6, 4, 5,2,3,1,8,2 };
        printArray(arr);

        System.out.println(mergeSortAndInvCount(arr1, 0, arr1.length - 1));
    }

    /**
     * 计算一个数组的叛序数
     * @param arr
     * @return
     */
    public static int getInvCount(int arr[]) {
        int n = arr.length;
        int inv_count = 0;
        for (int i = 0; i < n - 1; i++) {
            for (int j = i + 1; j < n; j++) {
                if (arr[i] > arr[j]) {
                    inv_count++;
                }
            }
        }

        return inv_count;
    }

    /**
     * 计算一个数组的叛序数并排序
     * @param arr
     * @return
     */
    public static int mergeSortAndInvCount(int[] arr, int l, int r) {

        // Keeps track of the inversion count at a particular node of the recursion tree
        int count = 0;

        if (l < r) {
            int m = (l + r) / 2;

            // Total inversion count = left subarray count
            // + right subarray count + merge count

            // Left subarray count
            count += mergeSortAndInvCount(arr, l, m);

            // Right subarray count
            count += mergeSortAndInvCount(arr, m + 1, r);

            // Merge count
            count += mergeAndCount(arr, l, m, r);
        }

        return count;
    }

    // Function to count the number of inversions
    // during the merge process
    private static int mergeAndCount(int[] arr, int l, int m, int r) {
        // Left subarray
        int[] left = Arrays.copyOfRange(arr, l, m + 1);

        // Right subarray
        int[] right = Arrays.copyOfRange(arr, m + 1, r + 1);

        int i = 0, j = 0, k = l, swaps = 0;

        while (i < left.length && j < right.length) {
            if (left[i] <= right[j]) {
                arr[k++] = left[i++];
            }else {
                arr[k++] = right[j++];
                swaps += (m + 1) - (l + i);
            }
        }
        while (i < left.length) {
            arr[k++] = left[i++];
        }
        while (j < right.length) {
            arr[k++] = right[j++];
        }
        return swaps;
    }

    /* A utility function to print array of size n */
    private static void printArray(int arr[]) {
        int n = arr.length;
        for (int i = 0; i < n; ++i) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }
}

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