Merge Sort 归并排序
归并排序（Merge Sort）是一种常用的排序算法，其思路如下：
- 将待排序数组分成两个子数组，分别对两个子数组进行递归排序。
- 将两个已排序的子数组合并成一个有序数组。
以下是归并排序的具体步骤：
- 将待排序数组从中间分成两个子数组。
- 递归地对左右两个子数组进行归并排序。
- 将两个已排序的子数组合并成一个有序数组。
以下是归并排序的示例代码：
public class Sort { public static void mergeSort(int[] arr, int left, int right) { if (left < right) { int mid = (left + right) / 2; mergeSort(arr, left, mid); // 对左子数组进行递归排序 mergeSort(arr, mid + 1, right); // 对右子数组进行递归排序 merge(arr, left, mid, right); // 合并两个已排序的子数组 } } private static void merge(int[] arr, int left, int mid, int right) { int n1 = mid - left + 1; int n2 = right - mid; int[] leftArr = new int[n1]; int[] rightArr = new int[n2]; for (int i = 0; i < n1; i++) { leftArr[i] = arr[left + i]; } for (int j = 0; j < n2; j++) { rightArr[j] = arr[mid + 1 + j]; } int i = 0; int j = 0; int k = left; while (i < n1 && j < n2) { if (leftArr[i] <= rightArr[j]) { arr[k] = leftArr[i]; i++; } else { arr[k] = rightArr[j]; j++; } k++; } while (i < n1) { arr[k] = leftArr[i]; i++; k++; } while (j < n2) { arr[k] = rightArr[j]; j++; k++; } } public static void main(String[] args) { int[] array = {5, 2, 8, 12, 1, 6}; mergeSort(array); System.out.println("排序结果："); for (int num : array) { System.out.print(num + " "); } } }
归并排序的时间复杂度始终为O(n log n)，无论是最好情况、最坏情况还是平均情况下。
归并排序的空间复杂度为O(n)，因为需要使用额外的空间来存储临时数组。
归并排序是一种稳定的排序算法，适用于各种数据规模。
