跳转至

Java 归并排序：原理、实现与最佳实践

简介

归并排序（Merge Sort）是一种经典的排序算法，它采用分治法（Divide and Conquer）的策略。该算法的核心思想是将一个大问题分解为多个小问题，分别解决这些小问题，最后将小问题的解合并起来得到原问题的解。在 Java 中，归并排序可以高效地对数组或列表进行排序，时间复杂度为 $O(n log n)$，具有较好的稳定性。本文将详细介绍归并排序在 Java 中的基础概念、使用方法、常见实践以及最佳实践。

目录

  1. 归并排序的基础概念
  2. Java 中归并排序的使用方法
  3. 常见实践
  4. 最佳实践
  5. 小结
  6. 参考资料

1. 归并排序的基础概念

分治法思想

归并排序使用分治法，具体步骤如下： - 分解（Divide）：将待排序的数组分成两个子数组，递归地对这两个子数组进行排序。 - 解决（Conquer）：当子数组的长度为 1 或 0 时，认为该子数组已经有序。 - 合并（Merge）：将两个已排序的子数组合并成一个有序的数组。

时间复杂度和稳定性

  • 时间复杂度：归并排序的时间复杂度为 $O(n log n)$，其中 $n$ 是数组的长度。这是因为每次将数组分成两半需要 $log n$ 次，而每次合并操作需要 $O(n)$ 的时间。
  • 稳定性：归并排序是一种稳定的排序算法，即相等元素的相对顺序在排序前后保持不变。

2. Java 中归并排序的使用方法

下面是一个简单的 Java 实现归并排序的代码示例：

public class MergeSort {
    public static void mergeSort(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return;
        }
        int[] temp = new int[arr.length];
        mergeSort(arr, temp, 0, arr.length - 1);
    }

    private static void mergeSort(int[] arr, int[] temp, int left, int right) {
        if (left < right) {
            int mid = left + (right - left) / 2;
            // 递归排序左半部分
            mergeSort(arr, temp, left, mid);
            // 递归排序右半部分
            mergeSort(arr, temp, mid + 1, right);
            // 合并两个有序子数组
            merge(arr, temp, left, mid, right);
        }
    }

    private static void merge(int[] arr, int[] temp, int left, int mid, int right) {
        // 将原数组复制到临时数组
        System.arraycopy(arr, left, temp, left, right - left + 1);

        int i = left;
        int j = mid + 1;
        int k = left;

        // 合并两个子数组
        while (i <= mid && j <= right) {
            if (temp[i] <= temp[j]) {
                arr[k] = temp[i];
                i++;
            } else {
                arr[k] = temp[j];
                j++;
            }
            k++;
        }

        // 处理左半部分剩余元素
        while (i <= mid) {
            arr[k] = temp[i];
            i++;
            k++;
        }
    }

    public static void main(String[] args) {
        int[] arr = {5, 3, 8, 4, 2, 7, 1, 6};
        mergeSort(arr);
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

代码解释

  • mergeSort(int[] arr)：这是对外提供的排序方法，首先检查数组是否为空或长度是否小于等于 1，如果是则直接返回。然后创建一个临时数组 temp，并调用递归的 mergeSort 方法。
  • mergeSort(int[] arr, int[] temp, int left, int right)：递归地对数组进行分解，直到子数组的长度为 1 或 0，然后调用 merge 方法合并两个有序子数组。
  • merge(int[] arr, int[] temp, int left, int mid, int right)：将两个有序子数组合并成一个有序数组。首先将原数组的元素复制到临时数组中，然后比较两个子数组的元素，将较小的元素依次放入原数组中。

3. 常见实践

对对象数组进行排序

如果要对对象数组进行排序，需要实现 Comparable 接口或使用 Comparator 接口。以下是一个对自定义对象数组进行排序的示例：

import java.util.Arrays;

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

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

    public int getAge() {
        return age;
    }

    @Override
    public int compareTo(Person other) {
        return Integer.compare(this.age, other.age);
    }

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

public class ObjectMergeSort {
    public static void main(String[] args) {
        Person[] people = {
                new Person("Alice", 25),
                new Person("Bob", 20),
                new Person("Charlie", 30)
        };
        Arrays.sort(people);
        for (Person person : people) {
            System.out.println(person);
        }
    }
}

处理大规模数据

对于大规模数据的排序，可以使用多线程归并排序来提高性能。多线程归并排序将数组分成多个子数组，每个子数组由一个线程进行排序，最后将所有子数组合并。

4. 最佳实践

减少临时数组的创建

在上述代码中，每次递归调用都会创建一个临时数组，这会增加内存开销。可以在外部创建一个临时数组，避免重复创建。

public class OptimizedMergeSort {
    public static void mergeSort(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return;
        }
        int[] temp = new int[arr.length];
        mergeSort(arr, temp, 0, arr.length - 1);
    }

    private static void mergeSort(int[] arr, int[] temp, int left, int right) {
        if (left < right) {
            int mid = left + (right - left) / 2;
            mergeSort(arr, temp, left, mid);
            mergeSort(arr, temp, mid + 1, right);
            merge(arr, temp, left, mid, right);
        }
    }

    private static void merge(int[] arr, int[] temp, int left, int mid, int right) {
        System.arraycopy(arr, left, temp, left, right - left + 1);
        int i = left;
        int j = mid + 1;
        int k = left;

        while (i <= mid && j <= right) {
            if (temp[i] <= temp[j]) {
                arr[k] = temp[i];
                i++;
            } else {
                arr[k] = temp[j];
                j++;
            }
            k++;
        }

        while (i <= mid) {
            arr[k] = temp[i];
            i++;
            k++;
        }
    }

    public static void main(String[] args) {
        int[] arr = {5, 3, 8, 4, 2, 7, 1, 6};
        mergeSort(arr);
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

优化递归终止条件

当子数组的长度较小时，可以使用插入排序代替归并排序，因为插入排序在小规模数据上的性能更好。

5. 小结

归并排序是一种高效、稳定的排序算法，适用于各种规模的数据排序。在 Java 中实现归并排序时，需要注意临时数组的使用和递归的实现。通过优化临时数组的创建和递归终止条件，可以提高归并排序的性能。同时，归并排序也可以用于对对象数组进行排序，通过实现 Comparable 接口或使用 Comparator 接口来定义排序规则。

6. 参考资料

  • 《算法导论》
  • Java 官方文档
  • GeeksforGeeks 网站上的归并排序教程