常用的排序算法之归并排序（Merge Sort）
常用的排序算法之归并排序（Merge Sort）
归并排序（Merge Sort）
起源
归并排序（Merge Sort）的算法是由约翰·冯·诺依曼（John von Neumann）在1945年提出的。但在实际的计算机编程中，归并排序通常被认为是由计算机科学家罗伯特·塞奇威克（Robert Sedgewick）在《算法》（Algorithms）一书中提出的。
定义
归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。归并排序是一种稳定的排序方法。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。
引伸义
归并排序的核心思想是“分而治之”，它将一个大问题分解为若干个小问题来解决。在排序问题中，归并排序将待排序的数组分成若干个子数组，每个子数组都是一个有序的序列，然后再将这些有序的子数组合并成一个大的有序数组，从而实现对整个数组的排序。
优缺点
优点：
- 稳定性：归并排序是稳定的排序算法。
- 高效性：归并排序的时间复杂度为O(nlogn)，在数据量大的情况下，相比其他排序算法（如冒泡排序、插入排序）具有更高的效率。
- 可并行化：归并排序的分治思想使得算法具有很好的并行性，可以很容易地利用多线程或分布式系统来提高排序效率。
缺点：
- 空间复杂度：归并排序需要额外的空间来存储合并过程中的临时数据，因此其空间复杂度为O(n)。对于内存受限的场景，这可能是一个问题。
- 数据移动：归并排序在合并过程中可能会涉及大量的数据移动，这可能会增加算法的执行时间。
使用场景
归并排序适用于大数据量的排序场景，特别是在需要稳定排序或可以利用并行计算的情况下。例如，在数据库中排序大量数据时，归并排序是一个很好的选择。此外，归并排序还可以用于外部排序，即当数据量太大而无法一次性装入内存时，可以利用归并排序对多个磁盘上的文件进行排序。
使用数据一步步举例
假设有一个数组[38, 27, 43, 3, 9, 82, 10]，我们使用归并排序来对其进行升序排序：
- 分解：将数组分解成更小的子数组，直到子数组的大小为1。
[38], [27], [43], [3], [9], [82], [10]
- 递归进行排序并合并：开始合并相邻的子数组，并按大小排序。
- 合并
[38]和[27]，得到[27, 38] - 合并
[43]和[3]，得到[3, 43] - 合并
[9]和[82]，得到[9, 82] - 合并
[27, 38]和[3, 43]，得到[3, 27, 38, 43] - 合并
[9, 82]和[10]，得到[9, 10, 82] - 最后，合并
[3, 27, 38, 43]和[9, 10, 82]，得到[3, 9, 10, 27, 38, 43, 82]
- 合并
Java示例代码
import java.util.Arrays;
public class MergeSort {
public static void main(String[] args) {
int[] array = {38, 27, 43, 3, 9, 82, 10};
mergeSort(array, 0, array.length - 1);
System.out.println(Arrays.toString(array));
}
public static void mergeSort(int[] array, int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
mergeSort(array, left, mid);
mergeSort(array, mid + 1, right);
merge(array, left, mid, right);
}
}
public static void merge(int[] array, 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 (array[i] <= array[j]) {
temp[k++] = array[i++];
} else {
temp[k++] = array[j++];
}
}
// 把左边剩余的元素移到新数组中
while (i <= mid) {
temp[k++] = array[i++];
}
// 把右边剩余的元素移到新数组中
while (j <= right) {
temp[k++] = array[j++];
}
// 把新数组中的元素复制回原数组
for (int p = 0; p < temp.length; p++) {
array[left + p] = temp[p];
}
}
}在上面的代码中，mergeSort 方法是一个递归方法，它将数组分成两半，并对每一半递归地调用 mergeSort 方法。当数组被分成只包含一个元素的子数组时，递归停止。然后，merge 方法被用来合并两个已排序的子数组，形成一个更大的已排序数组。
main 方法中的 array 是要被排序的数组。mergeSort(array, 0, array.length - 1) 调用启动排序过程，其中 0 是数组的起始索引，array.length - 1 是数组的结束索引。排序完成后，Arrays.toString(array) 用于将排序后的数组打印到控制台。
腾讯云开发者
