Java实现归并排序算法

简介

归并排序（Merge Sort）是一种高效的、基于分治思想的排序算法。它的基本原理是将一个大的无序数组分成两个或多个较小的子数组，对这些子数组分别进行排序，然后再将排序好的子数组合并成一个有序的数组。在Java中实现归并排序算法，可以充分利用其面向对象和丰富的类库特性，为开发者提供一种简洁而有效的数据排序方式。

目录

1. 基础概念
2. 使用方法
3. 常见实践
4. 最佳实践
5. 代码示例
6. 小结
7. 参考资料

基础概念

分治思想

分治思想是归并排序的核心。“分”就是将一个大问题分解成若干个规模较小、相互独立且与原问题形式相同的子问题。“治”则是对这些子问题分别进行求解，然后将子问题的解合并成原问题的解。

合并操作

合并操作是归并排序中的关键步骤。它将两个已经排序的子数组合并成一个更大的有序数组。在合并过程中，通过比较两个子数组的元素，将较小的元素依次放入结果数组中，直到其中一个子数组的元素全部被处理完，然后将另一个子数组剩余的元素直接追加到结果数组的末尾。

使用方法

递归实现

1. 分解阶段：
   • 找到数组的中间位置，将数组分成两个子数组。
   • 对两个子数组分别递归调用归并排序算法，直到子数组的大小为1（此时子数组已经有序）。
2. 合并阶段：
   • 将两个已经排序的子数组合并成一个有序的数组。

迭代实现

迭代实现归并排序通常使用自底向上的方法。首先将数组分成大小为1的子数组（每个子数组本身就是有序的），然后逐步将相邻的子数组合并成更大的有序子数组，直到整个数组有序。

常见实践

对整数数组排序

在实际应用中，经常需要对整数数组进行排序。以下是一个简单的示例：

import java.util.Arrays;

public class MergeSortExample {
    public static void mergeSort(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return;
        }
        int mid = arr.length / 2;
        int[] left = Arrays.copyOfRange(arr, 0, mid);
        int[] right = Arrays.copyOfRange(arr, mid, arr.length);

        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("Original array: " + Arrays.toString(arr));
        mergeSort(arr);
        System.out.println("Sorted array: " + Arrays.toString(arr));
    }
}

对自定义对象数组排序

如果要对自定义对象数组进行排序，需要实现Comparable接口或使用Comparator接口。例如，对一个包含学生对象的数组按成绩排序：

import java.util.Arrays;
import java.util.Comparator;

class Student {
    private String name;
    private int score;

    public Student(String name, int score) {
        this.name = name;
        this.score = score;
    }

    public int getScore() {
        return score;
    }

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

public class CustomObjectMergeSort {
    public static void mergeSort(Student[] arr, Comparator<Student> comparator) {
        if (arr == null || arr.length <= 1) {
            return;
        }
        int mid = arr.length / 2;
        Student[] left = Arrays.copyOfRange(arr, 0, mid);
        Student[] right = Arrays.copyOfRange(arr, mid, arr.length);

        mergeSort(left, comparator);
        mergeSort(right, comparator);

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

    private static void merge(Student[] arr, Student[] left, Student[] right, Comparator<Student> comparator) {
        int i = 0, j = 0, k = 0;
        while (i < left.length && j < right.length) {
            if (comparator.compare(left[i], 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) {
        Student[] students = {
                new Student("Alice", 85),
                new Student("Bob", 70),
                new Student("Charlie", 90)
        };
        System.out.println("Original array: " + Arrays.toString(students));
        mergeSort(students, Comparator.comparingInt(Student::getScore));
        System.out.println("Sorted array: " + Arrays.toString(students));
    }
}

最佳实践

优化空间复杂度

递归实现的归并排序在分解数组时会创建额外的子数组，导致空间复杂度为O(n)。可以通过使用原地归并算法来优化空间复杂度，使其达到O(1)。不过原地归并算法实现起来相对复杂。

并行化处理

对于大规模数据，可以利用Java的多线程或并行流来并行化归并排序的分解和合并过程，提高排序效率。例如，可以使用Fork/Join框架来实现并行归并排序。

数据预处理

在进行归并排序之前，可以对数据进行一些预处理，例如去除重复元素或对数据进行大致的分组，以减少排序的工作量。

代码示例

完整的递归归并排序代码

import java.util.Arrays;

public class MergeSort {
    public static void mergeSort(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return;
        }
        int mid = arr.length / 2;
        int[] left = Arrays.copyOfRange(arr, 0, mid);
        int[] right = Arrays.copyOfRange(arr, mid, arr.length);

        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[] testArray = {10, 7, 8, 9, 1, 5};
        System.out.println("Before sorting: " + Arrays.toString(testArray));
        mergeSort(testArray);
        System.out.println("After sorting: " + Arrays.toString(testArray));
    }
}

迭代归并排序代码

import java.util.Arrays;

public class IterativeMergeSort {
    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, n);
                int endIndex = Math.min(startIndex + 2 * subArraySize, n);

                int[] left = Arrays.copyOfRange(arr, startIndex, midIndex);
                int[] right = Arrays.copyOfRange(arr, midIndex, endIndex);

                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[] testArray = {10, 7, 8, 9, 1, 5};
        System.out.println("Before sorting: " + Arrays.toString(testArray));
        mergeSort(testArray);
        System.out.println("After sorting: " + Arrays.toString(testArray));
    }
}

小结

归并排序是一种稳定、高效的排序算法，在Java中实现归并排序可以通过递归或迭代的方式。了解其基础概念、使用方法、常见实践和最佳实践，能够帮助开发者根据不同的应用场景选择合适的实现方式，提高排序效率和优化空间复杂度。通过不断练习和优化代码，开发者可以更好地掌握这一经典算法。

参考资料

• 《算法导论》（Thomas H. Cormen等著）
• Oracle Java Documentation
• 各种在线算法学习平台，如LeetCode、GeeksforGeeks等