归并排序java代码（归并排序java实现）

# 归并排序Java代码详解## 简介归并排序 (Merge Sort) 是一种高效的排序算法，它采用分治策略，将待排序的序列递归地划分为更小的子序列，直到每个子序列只包含一个元素（此时已排序）。然后，它将这些已排序的子序列合并成更大的已排序序列，最终得到整个序列的排序结果。归并排序的时间复杂度始终为 O(n log n)，即使在最坏情况下也是如此，并且它是一个稳定的排序算法，这意味着具有相同值的元素在排序后仍然保持其原始顺序。## 算法原理归并排序的核心思想是：1.

分治 (Divide):

将待排序的序列递归地分成两半，直到每个子序列只包含一个元素。 2.

排序 (Sort):

每个包含单个元素的子序列本身就是已排序的。 3.

合并 (Combine):

将两个已排序的子序列合并成一个更大的已排序序列。这个合并操作是算法的关键，它需要比较两个子序列的第一个元素，并将较小的元素放入新的已排序序列中，然后重复这个过程直到所有元素都被放入新的序列中。## Java代码实现以下是用Java实现的归并排序算法：```java public class MergeSort {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("Unsorted array:");printArray(arr);mergeSort(arr);System.out.println("\nSorted array:");printArray(arr);}private static void printArray(int[] arr) {for (int num : arr) {System.out.print(num + " ");}} } ```### 代码解释：

`mergeSort(int[] arr)`:

这是主递归函数，它将数组递归地分成两半，直到每个子数组只有一个元素。然后调用`merge()`函数来合并已排序的子数组。

`merge(int[] arr, int[] left, int[] right)`:

这个函数合并两个已排序的数组`left`和`right`，并将结果存储到`arr`中。它使用三个索引`i`、`j`和`k`分别跟踪`left`、`right`和`arr`中的位置。

`main()`:

这个函数是一个测试函数，它创建了一个未排序的数组，调用`mergeSort()`函数对其进行排序，然后打印排序后的数组。

`printArray()`:

这个函数用于打印数组的内容。## 时间和空间复杂度

时间复杂度:

O(n log n) 无论最佳、平均还是最坏情况都是如此。

空间复杂度:

O(n) 因为需要额外的空间来存储合并过程中生成的子数组。这是因为归并排序不是原地排序算法。## 总结归并排序是一种稳定、高效的排序算法，适用于各种规模的数据。尽管它需要额外的空间，但其稳定的时间复杂度使其成为许多应用中理想的选择，尤其是在需要保证排序稳定性的情况下。 理解其分治和合并策略对于掌握该算法至关重要。

归并排序Java代码详解

简介归并排序 (Merge Sort) 是一种高效的排序算法，它采用分治策略，将待排序的序列递归地划分为更小的子序列，直到每个子序列只包含一个元素（此时已排序）。然后，它将这些已排序的子序列合并成更大的已排序序列，最终得到整个序列的排序结果。归并排序的时间复杂度始终为 O(n log n)，即使在最坏情况下也是如此，并且它是一个稳定的排序算法，这意味着具有相同值的元素在排序后仍然保持其原始顺序。

算法原理归并排序的核心思想是：1. **分治 (Divide):** 将待排序的序列递归地分成两半，直到每个子序列只包含一个元素。 2. **排序 (Sort):** 每个包含单个元素的子序列本身就是已排序的。 3. **合并 (Combine):** 将两个已排序的子序列合并成一个更大的已排序序列。这个合并操作是算法的关键，它需要比较两个子序列的第一个元素，并将较小的元素放入新的已排序序列中，然后重复这个过程直到所有元素都被放入新的序列中。

Java代码实现以下是用Java实现的归并排序算法：```java public class MergeSort {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("Unsorted array:");printArray(arr);mergeSort(arr);System.out.println("\nSorted array:");printArray(arr);}private static void printArray(int[] arr) {for (int num : arr) {System.out.print(num + " ");}} } ```

代码解释：* **`mergeSort(int[] arr)`:** 这是主递归函数，它将数组递归地分成两半，直到每个子数组只有一个元素。然后调用`merge()`函数来合并已排序的子数组。 * **`merge(int[] arr, int[] left, int[] right)`:** 这个函数合并两个已排序的数组`left`和`right`，并将结果存储到`arr`中。它使用三个索引`i`、`j`和`k`分别跟踪`left`、`right`和`arr`中的位置。 * **`main()`:** 这个函数是一个测试函数，它创建了一个未排序的数组，调用`mergeSort()`函数对其进行排序，然后打印排序后的数组。 * **`printArray()`:** 这个函数用于打印数组的内容。

时间和空间复杂度* **时间复杂度:** O(n log n) 无论最佳、平均还是最坏情况都是如此。 * **空间复杂度:** O(n) 因为需要额外的空间来存储合并过程中生成的子数组。这是因为归并排序不是原地排序算法。

总结归并排序是一种稳定、高效的排序算法，适用于各种规模的数据。尽管它需要额外的空间，但其稳定的时间复杂度使其成为许多应用中理想的选择，尤其是在需要保证排序稳定性的情况下。 理解其分治和合并策略对于掌握该算法至关重要。