图解
归并排序是一种效率比较高的分治排序算法，主要分为两个步骤，分别为“分”和“并”。
-
分：将序列不断二分，直到每个子序列只有一个元素为止。
-
并：将相邻两个子序列进行合并，合并时比较两个子序列的元素大小，按照从小到大的顺序放入新的序列中。
是一种分治算法，在每轮排序中将待排序数组分成两部分，递归地将每个子数组排序，最后将两个排好序的子数组合并成一个有序数组。
具体实现如下：
-
将待排序数组分成两个子数组，每个子数组包含原数组的一半元素，如果原数组长度为奇数，则一个子数组比另一个多一个元素。
-
递归地对每个子数组进行归并排序，直到子数组长度为1。
-
合并两个排好序的子数组。将两个子数组中的最小元素依次比较，将较小的元素放入新数组中，直到其中一个子数组的元素全部被放入新数组中，此时将另一个子数组中的剩余元素直接放到新数组的尾部。
-
返回合并后的有序数组。
归并排序的时间复杂度为O(nlogn)，空间复杂度为O(n)。它是一种稳定的排序算法，适用于各种数据类型的排序。
以下是Java实现归并排序的代码：
public class MergeSort {
public static void mergeSort(int[] arr, int left, int right) {
if (left >= right) {
return;
}
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[] temp = new int[right - left + 1];
int i = left;
int j = mid + 1;
int k = 0;
while (i <= mid && j <= right) {
if (arr[i] <= arr[j]) {
temp[k++] = arr[i++];
} else {
temp[k++] = arr[j++];
}
}
while (i <= mid) {
temp[k++] = arr[i++];
}
while (j <= right) {
temp[k++] = arr[j++];
}
// 将排序后的元素拷贝回原数组
for (int p = 0; p < temp.length; p++) {
arr[left + p] = temp[p];
}
}
public static void main(String[] args) {
int[] arr = {5, 3, 8, 4, 2, 1, 10, 7};
mergeSort(arr, 0, arr.length - 1);
for (int i : arr) {
System.out.print(i + " ");
}
}
}
输出结果为：1 2 3 4 5 7 8 10
