归并排序

收录于

学习数据结构与算法

2021-05-17 14:29 · 阅读时长8分钟

归并排序采用分治的思想，通过不断的将数组一分为二，直到不可再分，然后对已排序的子数组递归合并，最后使得整个数组有序，归并排序的最好、最坏以及平均时间复杂度都是O(NlogN)。

算法的主要思路是

选取数组中间位置，将数组分为两个子数组。
继续对两个子数组执行1～2步操作，直到子数组中只有一个元素。
递归合并有序的子数组。

下面是数组[6, 5, 12, 10, 9, 1]使用归并排序算法进行排序的过程。

归并排序

等待开始

1/25

归并排序算法实现

1import java.util.Arrays;
2
3public class Main {
4    
5    public static void main(String[] args) {
6        int[] arr = {4, 5, 6, 1, 3, 2, 0};
7        mergeSort(arr, 0, arr.length - 1);
8        System.out.println(Arrays.toString(arr));
9    }
10    
11    public static void mergeSort(int[] arr, int left, int right) {
12        if (left == right) {
13            return;
14        }
15        int mid = (left + right) / 2;
16        mergeSort(arr, left, mid);
17        mergeSort(arr, mid + 1, right);
18        merge(arr, left, mid, right);
19    }
20
21    public static void merge(int[] arr, int left, int mid, int right) {
22        /**
23         * 建议放到全局，这样可以减少递归分配的内存
24         */
25        int[] sortedArray = new int[right - left + 1];
26        int i = left, j = mid + 1, k = 0;
27        while (i <= mid && j <= right) {
28            if (arr[i] <= arr[j]) {
29                sortedArray[k++] = arr[i++];
30            } else {
31                sortedArray[k++] = arr[j++];
32            }
33        }
34        while (i <= mid) {
35            sortedArray[k++] = arr[i++];
36        }
37        while (j <= right) {
38            sortedArray[k++] = arr[j++];
39        }
40        for (i = left; i <= right; i++) {
41            arr[i] = sortedArray[i - left];
42        }
43    }
44}
45

import java.util.Arrays;

public class Main {
    
    public static void main(String[] args) {
        int[] arr = {4, 5, 6, 1, 3, 2, 0};
        mergeSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }
    
    public static void mergeSort(int[] arr, int left, int right) {
        if (left == right) {
            return;
        }
        int mid = (left + right) / 2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }

public static void merge(int[] arr, int left, int mid, int right) {
        /**
         * 建议放到全局，这样可以减少递归分配的内存
         */
        int[] sortedArray = new int[right - left + 1];
        int i = left, j = mid + 1, k = 0;
        while (i <= mid && j <= right) {
            if (arr[i] <= arr[j]) {
                sortedArray[k++] = arr[i++];
            } else {
                sortedArray[k++] = arr[j++];
            }
        }
        while (i <= mid) {
            sortedArray[k++] = arr[i++];
        }
        while (j <= right) {
            sortedArray[k++] = arr[j++];
        }
        for (i = left; i <= right; i++) {
            arr[i] = sortedArray[i - left];
        }
    }
}

注意: 这个Java运行环境不支持自定义包名，并且public class name必须是Main

归并排序虽然在数组排序上效率低于快速排序，但是对链表进行排序时，归并排序通常是最佳选择，因为链表无法通过索引访问，如果使用快速排序效率会低很多，而归并排序对随机访问依赖较小，所以能够高效的完成链表的排序。

另外由于归并排序在排序过程中，左右子数组的排序并无依赖关系，所以可以并行提高效率。

下面是使用归并排序算法对链表进行排序的实现。

1/**
2 * 链表归并排序算法实现
3 */
4class Node {
5    int val;
6    Node next;
7
8    Node() {
9    }
10
11    Node(int val) {
12        this.val = val;
13    }
14}
15
16class Main {
17
18    public static void main(String[] args) {
19        Node head = buildList(new int[]{4, 2, 1, 3, 7, 6, 5});
20        Node sortedHead = mergeSort(head);
21        printList(sortedHead);
22    }
23
24    /**
25     * 链表归并排序
26     *
27     * @param head 待排序链表
28     * @return 排序好的链表
29     */
30    public static Node mergeSort(Node head) {
31        if (head == null || head.next == null)
32            return head;
33        /**
34         * 1. 获取链表的中间位置
35         */
36        Node middle = getMiddle(head);
37        /**
38         * 2. 递归对左右两边的子链表进行归并排序
39         */
40        Node left = mergeSort(head);
41        Node right = mergeSort(middle);
42        /**
43         * 3. 合并已排序的链表
44         */
45        return merge(left, right);
46    }
47
48
49    /**
50     * 合并有序链表
51     *
52     * @param list1 待合并的有序链表1
53     * @param list2 待合并的有序链表2
54     * @return 合并好的有序链表
55     */
56    private static Node merge(Node list1, Node list2) {
57        /**
58         * 辅助节点
59         */
60        Node dummyHead = new Node();
61        Node tail = dummyHead;
62        while (list1 != null && list2 != null) {
63            if (list1.val < list2.val) {
64                tail.next = list1;
65                list1 = list1.next;
66            } else {
67                tail.next = list2;
68                list2 = list2.next;
69            }
70            tail = tail.next;
71        }
72        tail.next = (list1 != null) ? list1 : list2;
73        return dummyHead.next;
74    }
75
76    /**
77     * 通过快慢指针获取链表中间节点
78     *
79     * @param head 链表
80     * @return 中间节点
81     */
82    private static Node getMiddle(Node head) {
83        Node slow = null;
84        while (head != null && head.next != null) {
85            slow = (slow == null) ? head : slow.next;
86            head = head.next.next;
87        }
88        Node middle = slow.next;
89        slow.next = null;
90        return middle;
91    }
92
93    /**
94     * 通过数组构建链表
95     *
96     * @param arr 数组
97     * @return 链表
98     */
99    public static Node buildList(int[] arr) {
100        Node head = null, previous = null;
101        for (int i : arr) {
102            Node node = new Node(i);
103            if (head == null) {
104                head = node;
105            } else {
106                previous.next = node;
107            }
108            previous = node;
109        }
110        return head;
111    }
112
113    /**
114     * 打印链表
115     *
116     * @param head 链表
117     */
118    public static void printList(Node head) {
119        StringBuilder sb = new StringBuilder();
120        while (head != null) {
121            sb.append(head.val).append(" ");
122            head = head.next;
123        }
124        System.out.println(sb);
125    }
126}
127

/**
 * 链表归并排序算法实现
 */
class Node {
    int val;
    Node next;

Node() {
    }

Node(int val) {
        this.val = val;
    }
}

class Main {

public static void main(String[] args) {
        Node head = buildList(new int[]{4, 2, 1, 3, 7, 6, 5});
        Node sortedHead = mergeSort(head);
        printList(sortedHead);
    }

/**
     * 链表归并排序
     *
     * @param head 待排序链表
     * @return 排序好的链表
     */
    public static Node mergeSort(Node head) {
        if (head == null || head.next == null)
            return head;
        /**
         * 1. 获取链表的中间位置
         */
        Node middle = getMiddle(head);
        /**
         * 2. 递归对左右两边的子链表进行归并排序
         */
        Node left = mergeSort(head);
        Node right = mergeSort(middle);
        /**
         * 3. 合并已排序的链表
         */
        return merge(left, right);
    }

/**
     * 合并有序链表
     *
     * @param list1 待合并的有序链表1
     * @param list2 待合并的有序链表2
     * @return 合并好的有序链表
     */
    private static Node merge(Node list1, Node list2) {
        /**
         * 辅助节点
         */
        Node dummyHead = new Node();
        Node tail = dummyHead;
        while (list1 != null && list2 != null) {
            if (list1.val < list2.val) {
                tail.next = list1;
                list1 = list1.next;
            } else {
                tail.next = list2;
                list2 = list2.next;
            }
            tail = tail.next;
        }
        tail.next = (list1 != null) ? list1 : list2;
        return dummyHead.next;
    }

/**
     * 通过快慢指针获取链表中间节点
     *
     * @param head 链表
     * @return 中间节点
     */
    private static Node getMiddle(Node head) {
        Node slow = null;
        while (head != null && head.next != null) {
            slow = (slow == null) ? head : slow.next;
            head = head.next.next;
        }
        Node middle = slow.next;
        slow.next = null;
        return middle;
    }

/**
     * 通过数组构建链表
     *
     * @param arr 数组
     * @return 链表
     */
    public static Node buildList(int[] arr) {
        Node head = null, previous = null;
        for (int i : arr) {
            Node node = new Node(i);
            if (head == null) {
                head = node;
            } else {
                previous.next = node;
            }
            previous = node;
        }
        return head;
    }

/**
     * 打印链表
     *
     * @param head 链表
     */
    public static void printList(Node head) {
        StringBuilder sb = new StringBuilder();
        while (head != null) {
            sb.append(head.val).append(" ");
            head = head.next;
        }
        System.out.println(sb);
    }
}

注意: 这个Java运行环境不支持自定义包名，并且public class name必须是Main

归并排序排序算法

归并排序

学习数据结构与算法

选择排序

堆排序