归并排序算法的Java实现详解

资源摘要信息:"归并排序（Merge Sort）是一种高效的排序算法，采用分治法（Divide and Conquer）的一个非常典型的应用。归并排序的工作原理是将原始数组分成较小的数组，直到每个小数组只有一个位置，然后将小数组归并成较大的数组，直到最后只有一个排序完毕的大数组。因为归并排序总是将数组分成两半，因此它是一个分而治之的算法。由于它在排序时需要与原始数组同样大小的额外空间进行合并操作，所以归并排序不是原地排序算法。 在Java中实现归并排序算法通常涉及以下几个步骤： 1. 分割：将数组分割成两半。 2. 合并：将两个有序的半段数组合并成一个有序数组。 具体操作如下： - 首先，将数组从中间分割成两个子数组。 - 对每个子数组递归地应用归并排序，直到每个子数组只有一个元素（可以认为是已经排序的数组）。 - 然后，将排序好的子数组按照顺序合并起来，形成一个完全排序好的数组。 以下是归并排序在Java中的一个简单实现示例： ```java public class MergeSort { // 主函数，用于测试 public static void main(String[] args) { int[] array = {9, 3, 1, 5, 13, 12, 7}; MergeSort mergeSort = new MergeSort(); mergeSort.sort(array, 0, array.length - 1); System.out.println("Sorted array:"); for (int value : array) { System.out.print(value + " "); } } // 归并排序函数 public void sort(int[] array, int left, int right) { if (left < right) { // 找到中间位置 int middle = (left + right) / 2; // 对左边进行排序 sort(array, left, middle); // 对右边进行排序 sort(array, middle + 1, right); // 合并两部分 merge(array, left, middle, right); } } // 合并函数 public void merge(int[] array, int left, int middle, int right) { // 找到左右两个子数组的大小 int n1 = middle - left + 1; int n2 = right - middle; // 创建临时数组 int[] L = new int[n1]; int[] R = new int[n2]; // 复制数据到临时数组 System.arraycopy(array, left, L, 0, n1); System.arraycopy(array, middle + 1, R, 0, n2); // 合并临时数组回到原数组 int i = 0, j = 0, k = left; while (i < n1 && j < n2) { if (L[i] <= R[j]) { array[k] = L[i]; i++; } else { array[k] = R[j]; j++; } k++; } // 复制剩余的L[]，如果有的话 while (i < n1) { array[k] = L[i]; i++; k++; } // 复制剩余的R[]，如果有的话 while (j < n2) { array[k] = R[j]; j++; k++; } } } ``` 在上述Java代码中，`sort`方法是归并排序的主要方法，它递归地将数组分成更小的部分，并对它们进行排序。`merge`方法用于合并两个已排序的部分。当数组只有一个元素或为空时，就被认为是排序好的。递归继续直到子数组不能进一步分割，然后开始通过`merge`方法合并这些子数组，最终形成一个完全有序的数组。 归并排序的优点在于它有稳定的O(n log n)时间复杂度，对于大型数据集来说非常高效。并且，由于其稳定性和对链表等非连续存储结构的良好支持，归并排序在某些特定应用中非常有用。"