今天会是有Offer的一天么：面试时你真的会写归并排序么

Fawziya ·

更新时间:2024-11-10

· 736 次阅读

UP打算把八大排序算法中最难理解的几种整理一下，分别是归并排序、快排和堆排序。今天先介绍归并排序。

在这里插入图片描述

先说一下归并排序的图解

在这里插入图片描述
所谓的归并，是将两个或两个以上的有序文件合并成为一个新的有序文件，归并排序是把一个有n个记录的无序文件看成是由n个长度为1的有序子文件组成的文件，然后进行两两归并，如此重复，直至最后形成包含n个归并，得到n/2个长度为2或者1的有序文件，再两两归并，如此重复，直至最后形成包含n个记录的有序文件位置，这种反复将两个有序文件归并成一个有序文件的排序方法称为二路归并排序。

废话不多说直接上代码

import java.util.ArrayList;
import java.util.Arrays;
public class MergeSortTest {
    public static void main(String[] args) {
        int[] num = new int[]{12, 2, 3, 18, 9, 10, 21, 7, 6, 1, 23};
        System.out.println("需要排序的数组；" + Arrays.toString(num));
        MergeSort(num, 0, num.length - 1);
        System.out.println(Arrays.toString(num));
    }
    public static void MergeSort(int[] num, int left, int right) {
        int middle = (left + right) / 2;
        if (left >= right) {
            return;
        }
        MergeSort(num, left, middle);
        MergeSort(num, middle + 1, right);
        //注意这里
        Merge(num, left, middle, right);
        System.out.println(Arrays.toString(num));
    }
    public static void Merge(int[] num, int left, int middle, int right) {
        int[] num_copy = new int[right - left + 1];
        int left_copy = left;
        int right_copy = middle + 1;
        int index = 0;
        ///每次进行比较，把较小的数移入新数组
        while (left_copy <= middle && right_copy <= right) {
            if (num[left_copy] < num[right_copy]) {
                num_copy[index++] = num[left_copy++];
            } else {
                num_copy[index++] = num[right_copy++];
            }
        }
        //把左边剩余的数字移入数组
        while (left_copy <= middle) {
            num_copy[index++] = num[left_copy++];
        }
        //把右边剩余的数字移入数组
        while (right_copy <= right) {
            num_copy[index++] = num[right_copy++];
        }
        //覆盖旧数组
        for (int i = 0; i < num_copy.length; i++) {
            num[left + i] = num_copy[i];
        }
    }
}

在这里插入图片描述

是不是看起来很容易。归并排序主要包括两个方法。第一个方法是MergeSort，用于将数组进行分组，第二个方法Merge用于将两个有序数组进行合并。

在这里插入图片描述

Talk is easy，show me the code。接下来咱们来看一道非常经典的算法题目。可以使用我们的归并排序进行解决。 leetcode中文网第23题，这里可以使用我们刚刚学的归并排序进行解决。

在这里插入图片描述


public class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
        val = x;
    }
}
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists.length == 2) {
            return Merge(lists[0], lists[1]);
        }
        if (lists.length == 1) {
            return lists[0];
        }
        if (lists.length == 0) {
            return null;
        }
        int length = lists.length;
        ListNode[] node1 = new ListNode[length / 2];
        ListNode[] node2 = new ListNode[length - length / 2];
        int index = 0;
        //这里将lists拆分到两个数组中。
        for (; index < node1.length; index++) {
            node1[index] = lists[index];
        }
        for (int i = 0; i  node2.val) {
            node3 = node2;
            node4 = node2;
            node2 = node2.next;
        } else {
            node3 = node1;
            node4 = node1;
            node1 = node1.next;
        }
        ///比较排序构建链表
        while (node1 != null && node2 != null) {
            if (node1.val > node2.val) {
                node3.next = node2;
                node3 = node2;
                node2 = node2.next;
            } else {
                node3.next = node1;
                node3 = node1;
                node1 = node1.next;
            }
        }
        //node1可能不为空，还要继续添加判断
        while (node1 != null) {
            node3.next = node1;
            node3 = node1;
            node1 = node1.next;
        }
        //同理node2也可能不为空，要继续添加节点
        while (node2 != null) {
            node3.next = node2;
            node3 = node2;
            node2 = node2.next;
        }
        //返回我们的头结点
        return node4;
    }
}

这里的MergeKLists方法类似于我们代码一中的MergeSort方法。

在这里插入图片描述