Java 中的归并排序程序

简介

归并排序（Merge Sort）是一种高效的、基于分治思想的排序算法。在 Java 编程中，归并排序被广泛应用于需要对大量数据进行快速、稳定排序的场景。本文将详细介绍 Java 中归并排序程序的基础概念、使用方法、常见实践以及最佳实践，帮助读者深入理解并能高效运用这一算法。

目录

1. 基础概念
2. 使用方法
   • 递归实现
   • 迭代实现
3. 常见实践
   • 对整数数组排序
   • 对自定义对象数组排序
4. 最佳实践
   • 优化策略
   • 与其他排序算法结合
5. 小结
6. 参考资料

基础概念

归并排序的核心思想是“分而治之”（Divide and Conquer）。具体步骤如下： 1. 分解（Divide）：将一个大的、未排序的数组分成两个或多个较小的子数组，直到每个子数组只包含一个元素（或非常小的规模）。 2. 解决（Conquer）：对每个较小的子数组进行排序，通常可以使用简单的排序方法（在归并排序中，这一步往往是递归进行的）。 3. 合并（Merge）：将排序好的子数组合并成一个有序的大数组。

归并排序是一种稳定的排序算法，这意味着相等的元素在排序前后的相对顺序保持不变。它的时间复杂度为 $O(n log n)$，空间复杂度为 $O(n)$，其中 $n$ 是数组的长度。

使用方法

递归实现

以下是 Java 中归并排序递归实现的代码示例：

public class MergeSortRecursive {

    public static void mergeSort(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return;
        }
        int mid = arr.length / 2;
        int[] left = new int[mid];
        int[] right = new int[arr.length - mid];

        System.arraycopy(arr, 0, left, 0, mid);
        System.arraycopy(arr, mid, right, 0, arr.length - mid);

        mergeSort(left);
        mergeSort(right);

        merge(arr, left, right);
    }

    private static void merge(int[] arr, int[] left, int[] right) {
        int i = 0, j = 0, k = 0;

        while (i < left.length && j < right.length) {
            if (left[i] <= right[j]) {
                arr[k++] = left[i++];
            } else {
                arr[k++] = right[j++];
            }
        }

        while (i < left.length) {
            arr[k++] = left[i++];
        }

        while (j < right.length) {
            arr[k++] = right[j++];
        }
    }

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

        mergeSort(arr);

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

迭代实现

迭代实现归并排序相对复杂一些，但它避免了递归调用带来的栈空间开销。以下是迭代实现的代码示例：

public class MergeSortIterative {

    public static void mergeSort(int[] arr) {
        int n = arr.length;
        for (int subArraySize = 1; subArraySize < n; subArraySize *= 2) {
            for (int startIndex = 0; startIndex < n; startIndex += 2 * subArraySize) {
                int midIndex = Math.min(startIndex + subArraySize - 1, n - 1);
                int endIndex = Math.min(startIndex + 2 * subArraySize - 1, n - 1);

                int[] left = new int[midIndex - startIndex + 1];
                int[] right = new int[endIndex - midIndex];

                System.arraycopy(arr, startIndex, left, 0, left.length);
                System.arraycopy(arr, midIndex + 1, right, 0, right.length);

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

    private static void merge(int[] arr, int[] left, int[] right, int startIndex) {
        int i = 0, j = 0, k = startIndex;

        while (i < left.length && j < right.length) {
            if (left[i] <= right[j]) {
                arr[k++] = left[i++];
            } else {
                arr[k++] = right[j++];
            }
        }

        while (i < left.length) {
            arr[k++] = left[i++];
        }

        while (j < right.length) {
            arr[k++] = right[j++];
        }
    }

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

        mergeSort(arr);

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

常见实践

对整数数组排序

上述代码示例已经展示了如何对整数数组进行归并排序。在实际应用中，只需要将待排序的整数数组传递给 mergeSort 方法即可。

对自定义对象数组排序

如果要对自定义对象数组进行排序，需要让自定义类实现 Comparable 接口，并实现 compareTo 方法来定义比较规则。以下是一个示例：

class Person implements Comparable<Person> {
    private String name;
    private int age;

    public Person(String name, int age) {
        this.name = name;
        this.age = age;
    }

    @Override
    public int compareTo(Person other) {
        return this.age - other.age; // 按年龄升序排序
    }

    @Override
    public String toString() {
        return "Person{" +
                "name='" + name + '\'' +
                ", age=" + age +
                '}';
    }
}

public class MergeSortCustomObject {

    public static void mergeSort(Comparable[] arr) {
        if (arr == null || arr.length <= 1) {
            return;
        }
        int mid = arr.length / 2;
        Comparable[] left = new Comparable[mid];
        Comparable[] right = new Comparable[arr.length - mid];

        System.arraycopy(arr, 0, left, 0, mid);
        System.arraycopy(arr, mid, right, 0, arr.length - mid);

        mergeSort(left);
        mergeSort(right);

        merge(arr, left, right);
    }

    private static void merge(Comparable[] arr, Comparable[] left, Comparable[] right) {
        int i = 0, j = 0, k = 0;

        while (i < left.length && j < right.length) {
            if (left[i].compareTo(right[j]) <= 0) {
                arr[k++] = left[i++];
            } else {
                arr[k++] = right[j++];
            }
        }

        while (i < left.length) {
            arr[k++] = left[i++];
        }

        while (j < right.length) {
            arr[k++] = right[j++];
        }
    }

    public static void main(String[] args) {
        Person[] people = {
                new Person("Alice", 25),
                new Person("Bob", 20),
                new Person("Charlie", 30)
        };

        System.out.println("Before sorting:");
        for (Person person : people) {
            System.out.println(person);
        }

        mergeSort(people);

        System.out.println("\nAfter sorting:");
        for (Person person : people) {
            System.out.println(person);
        }
    }
}

最佳实践

优化策略

1. 减少临时数组的创建：在合并步骤中，可以尝试复用已有的数组空间，减少不必要的临时数组创建，从而降低空间复杂度。
2. 使用插入排序优化小数组：当子数组规模较小时，归并排序的递归开销可能会超过其优势。此时可以切换到插入排序，插入排序在小数组上表现更好。

与其他排序算法结合

在实际应用中，可以将归并排序与其他排序算法结合使用。例如，在数据规模较小或者数据基本有序的情况下，可以先使用插入排序或冒泡排序，然后再使用归并排序对整个数据集进行排序，以提高整体性能。

小结

本文详细介绍了 Java 中的归并排序程序，包括基础概念、递归和迭代实现方法、常见实践以及最佳实践。归并排序作为一种高效、稳定的排序算法，在各种数据处理场景中都有广泛应用。通过深入理解和掌握归并排序的原理和实现，读者可以在实际编程中灵活运用这一算法，提高程序的性能和效率。

参考资料

• 《算法导论》（Introduction to Algorithms）
• Oracle Java 官方文档
• 各大在线编程学习平台（如 LeetCode、GeeksforGeeks 等）上关于归并排序的教程和练习题