跳转至

Java 中的归并排序程序

简介

归并排序（Merge Sort）是一种高效的、基于分治思想的排序算法。在计算机科学领域，排序算法是基础且重要的工具，而归并排序以其稳定的性能和相对高效的时间复杂度在众多排序算法中占据重要地位。本文将详细介绍如何在 Java 中实现归并排序程序，涵盖基础概念、使用方法、常见实践以及最佳实践等方面，帮助读者全面掌握这一算法在 Java 环境中的应用。

目录

  1. 归并排序基础概念
  2. Java 中归并排序的使用方法
    • 代码示例
  3. 常见实践
    • 数组排序
    • 链表排序
  4. 最佳实践
    • 优化策略
  5. 小结
  6. 参考资料

归并排序基础概念

归并排序遵循分治（Divide and Conquer）策略，其核心思想可以概括为三个步骤： 1. 分解（Divide）：将一个大问题分解为多个规模较小、相互独立且结构相同的子问题。在排序数组的场景下，就是将一个大数组不断地分成两个较小的子数组。 2. 解决（Conquer）：递归地解决这些子问题，也就是对每个子数组进行排序。 3. 合并（Combine）：将子问题的解合并起来，得到原问题的解。在归并排序中，这一步是将两个已经排序的子数组合并成一个有序的数组。

归并排序的时间复杂度为 $O(n log n)$，其中 $n$ 是待排序元素的数量。这使得它在处理大规模数据时表现出色，尤其适用于对稳定性有要求的场景。

Java 中归并排序的使用方法

下面是一个在 Java 中实现归并排序的完整代码示例：

public class MergeSort {

    // 合并两个有序子数组
    private static void merge(int[] arr, int left, int mid, int right) {
        int n1 = mid - left + 1;
        int n2 = right - mid;

        int[] L = new int[n1];
        int[] R = new int[n2];

        for (int i = 0; i < n1; ++i)
            L[i] = arr[left + i];
        for (int j = 0; j < n2; ++j)
            R[j] = arr[mid + 1 + j];

        int i = 0, j = 0;
        int k = left;

        while (i < n1 && j < n2) {
            if (L[i] <= R[j]) {
                arr[k] = L[i];
                i++;
            } else {
                arr[k] = R[j];
                j++;
            }
            k++;
        }

        while (i < n1) {
            arr[k] = L[i];
            i++;
            k++;
        }

        while (j < n2) {
            arr[k] = R[j];
            j++;
            k++;
        }
    }

    // 归并排序主方法
    public static void mergeSort(int[] arr, int left, int right) {
        if (left < right) {
            int mid = (left + right) / 2;

            mergeSort(arr, left, mid);
            mergeSort(arr, mid + 1, right);

            merge(arr, left, mid, right);
        }
    }

    public static void main(String[] args) {
        int[] arr = {12, 11, 13, 5, 6, 7};
        System.out.println("Unsorted array:");
        for (int num : arr) {
            System.out.print(num + " ");
        }

        mergeSort(arr, 0, arr.length - 1);

        System.out.println("\nSorted array:");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

代码说明

  1. merge 方法：该方法负责将两个有序的子数组合并成一个有序的数组。它首先创建两个临时数组 L 和 R，分别存储两个子数组的元素。然后通过比较两个临时数组的元素，将较小的元素依次放入原数组中，直到其中一个临时数组遍历完。最后，将剩余的元素也放入原数组。
  2. mergeSort 方法：这是归并排序的递归实现。它首先检查 left 是否小于 right，如果是，则计算中间索引 mid。然后递归地对左半部分和右半部分进行排序，最后调用 merge 方法将两个有序的子数组合并。
  3. main 方法：在 main 方法中，我们创建了一个未排序的数组，并调用 mergeSort 方法对其进行排序，最后输出排序前后的数组。

常见实践

数组排序

上述代码示例展示了如何对整数数组进行归并排序。在实际应用中，我们可以根据需要对不同类型的数组进行排序，例如字符串数组、自定义对象数组等。对于自定义对象数组，我们需要实现 Comparable 接口或者提供一个 Comparator 来定义对象之间的比较规则。

链表排序

归并排序同样适用于链表。由于链表的特性，在实现链表的归并排序时，我们需要特别注意指针的操作。以下是一个简单的 Java 代码示例，用于对链表进行归并排序：

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

public class MergeSortLinkedList {

    public ListNode mergeSort(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        ListNode slow = head;
        ListNode fast = head;
        ListNode prev = null;

        while (fast != null && fast.next != null) {
            prev = slow;
            slow = slow.next;
            fast = fast.next.next;
        }

        prev.next = null;

        ListNode left = mergeSort(head);
        ListNode right = mergeSort(slow);

        return merge(left, right);
    }

    private ListNode merge(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;

        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                tail.next = l1;
                l1 = l1.next;
            } else {
                tail.next = l2;
                l2 = l2.next;
            }
            tail = tail.next;
        }

        if (l1 != null) {
            tail.next = l1;
        }

        if (l2 != null) {
            tail.next = l2;
        }

        return dummy.next;
    }

    public static void main(String[] args) {
        MergeSortLinkedList solution = new MergeSortLinkedList();

        ListNode head = new ListNode(4);
        head.next = new ListNode(2);
        head.next.next = new ListNode(1);
        head.next.next.next = new ListNode(3);

        ListNode sortedHead = solution.mergeSort(head);

        while (sortedHead != null) {
            System.out.print(sortedHead.val + " ");
            sortedHead = sortedHead.next;
        }
    }
}

代码说明

  1. mergeSort 方法：在链表的归并排序中，我们首先使用快慢指针找到链表的中间节点，将链表分成两个子链表。然后递归地对这两个子链表进行排序，最后调用 merge 方法将两个有序的子链合并并成一个有序链表。
  2. merge 方法：该方法负责合并两个有序链表。它创建一个虚拟头节点 dummy，通过比较两个链表的节点值，将较小的节点依次连接到 dummy 链表的后面，直到其中一个链表遍历完。最后，将剩余的链表连接到 dummy 链表的末尾。

最佳实践

优化策略

  1. 减少临时数组的创建：在合并过程中，我们可以尝试减少临时数组的创建次数。例如，可以预先分配足够大的临时数组，避免在每次递归调用时都创建新的临时数组。
  2. 插入排序优化：对于小规模数据，插入排序的性能可能优于归并排序。因此，我们可以在递归到小规模子数组时，切换到插入排序，以提高整体性能。
public class OptimizedMergeSort {

    private static final int INSERTION_SORT_THRESHOLD = 16;

    private static void insertionSort(int[] arr, int left, int right) {
        for (int i = left + 1; i <= right; i++) {
            int key = arr[i];
            int j = i - 1;
            while (j >= left && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = key;
        }
    }

    private static void merge(int[] arr, int left, int mid, int right) {
        int n1 = mid - left + 1;
        int n2 = right - mid;

        int[] L = new int[n1];
        int[] R = new int[n2];

        for (int i = 0; i < n1; ++i)
            L[i] = arr[left + i];
        for (int j = 0; j < n2; ++j)
            R[j] = arr[mid + 1 + j];

        int i = 0, j = 0;
        int k = left;

        while (i < n1 && j < n2) {
            if (L[i] <= R[j]) {
                arr[k] = L[i];
                i++;
            } else {
                arr[k] = R[j];
                j++;
            }
            k++;
        }

        while (i < n1) {
            arr[k] = L[i];
            i++;
            k++;
        }

        while (j < n2) {
            arr[k] = R[j];
            j++;
            k++;
        }
    }

    public static void mergeSort(int[] arr, int left, int right) {
        if (left < right) {
            if (right - left + 1 <= INSERTION_SORT_THRESHOLD) {
                insertionSort(arr, left, right);
            } else {
                int mid = (left + right) / 2;

                mergeSort(arr, left, mid);
                mergeSort(arr, mid + 1, right);

                merge(arr, left, mid, right);
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {12, 11, 13, 5, 6, 7};
        System.out.println("Unsorted array:");
        for (int num : arr) {
            System.out.print(num + " ");
        }

        mergeSort(arr, 0, arr.length - 1);

        System.out.println("\nSorted array:");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

代码说明

在上述优化后的代码中，我们添加了一个 insertionSort 方法，并在 mergeSort 方法中判断子数组的大小。如果子数组的大小小于等于 INSERTION_SORT_THRESHOLD（这里设置为 16），则调用 insertionSort 方法进行排序，否则继续使用归并排序。

小结

归并排序是一种强大且稳定的排序算法，在 Java 中实现归并排序需要理解其分治思想，并掌握数组和链表的操作技巧。通过合理的优化策略，我们可以进一步提高归并排序的性能。希望本文的介绍和代码示例能够帮助读者更好地理解和应用 Java 中的归并排序算法。

参考资料

  1. 《算法导论》（Introduction to Algorithms）
  2. Oracle Java 官方文档
  3. 各大在线编程学习平台相关教程

以上就是关于 Java 中归并排序程序的详细介绍，希望对你有所帮助。如果你有任何疑问或建议，欢迎留言讨论。