JAVA十大排序算法之归并排序详解
JAVA十大排序算法之归并排序详解
一、概述
归并排序是一种高效稳定的排序算法，它将待排序的序列分成若干个子序列，每个子序列都是有序的，然后再将有序的子序列合并成整体有序的序列。由于归并排序是基于比较的排序算法，因此时间复杂度为 O(nlogn)。
二、算法流程
归并排序算法分为两个过程：分治和合并。
-
分治：将待排序的序列平分成两个子序列，对左右两个子序列分别进行递归排序。当子序列长度小于等于1时，停止递归。
-
合并：将排好序的左右子序列合并成一个有序的序列。
三、JAVA代码实现
public static void mergeSort(int[] arr, int low, int high) {
if (low < high) {
int mid = (low + high) / 2;
// 递归分治
mergeSort(arr, low, mid);
mergeSort(arr, mid + 1, high);
// 合并子序列
merge(arr, low, mid, high);
}
}
private static void merge(int[] arr, int low, int mid, int high) {
int[] temp = new int[high - low + 1];
int i = low;
int j = mid + 1;
int k = 0;
// 比较左右子序列，合并成一个有序的序列
while (i <= mid && j <= high) {
if (arr[i] <= arr[j]) {
temp[k++] = arr[i++];
} else {
temp[k++] = arr[j++];
}
}
while (i <= mid) {
temp[k++] = arr[i++];
}
while (j <= high) {
temp[k++] = arr[j++];
}
// 将临时数组中的元素复制到原数组中
for (int m = 0; m < temp.length; m++) {
arr[low + m] = temp[m];
}
}
在上面的代码中，mergeSort() 方法是归并排序的入口方法，merge() 方法是合并两个子序列的方法。
四、示例说明
示例一
对于待排序序列 [5, 3, 6, 8, 4, 2]，按照归并排序的流程，分别进行以下操作：
-
分治：将待排序的序列分成
[5, 3, 6]和[8, 4, 2]两个子序列，对子序列进行递归排序。-
[5, 3, 6]：将子序列分成[5, 3]和[6]两个子序列，对子序列进行递归排序。-
[5, 3]：将子序列分成[5]和[3]两个子序列，对子序列进行递归排序。[5]和[3]都只有一个元素，递归终止。
-
[6]：只有一个元素，递归终止。
-
-
[8, 4, 2]：将子序列分成[8]和[4, 2]两个子序列，对子序列进行递归排序。-
[4, 2]：将子序列分成[4]和[2]两个子序列，对子序列进行递归排序。[4]和[2]都只有一个元素，递归终止。
-
[8]：只有一个元素，递归终止。
-
-
-
合并：将排好序的子序列合并成有序的序列。首先将
[5]和[3]合并成[3, 5]，然后将[6]和[3, 5]合并成[3, 5, 6]。将[4]和[2]合并成[2, 4]，然后将[8]和[2, 4]合并成[2, 4, 8]。最后将[3, 5, 6]和[2, 4, 8]合并成[2, 3, 4, 5, 6, 8]。完成排序。
示例二
对于待排序序列 [7, 4, 3, 8, 1, 5]，按照归并排序的流程，分别进行以下操作：
-
分治：将待排序的序列分成
[7, 4, 3]和[8, 1, 5]两个子序列，对子序列进行递归排序。-
[7, 4, 3]：将子序列分成[7]和[4, 3]两个子序列，对子序列进行递归排序。-
[4, 3]：将子序列分成[4]和[3]两个子序列，对子序列进行递归排序。[4]和[3]都只有一个元素，递归终止。
-
[7]：只有一个元素，递归终止。
-
-
[8, 1, 5]：将子序列分成[8]和[1, 5]两个子序列，对子序列进行递归排序。-
[1, 5]：将子序列分成[1]和[5]两个子序列，对子序列进行递归排序。[1]和[5]都只有一个元素，递归终止。
-
[8]：只有一个元素，递归终止。
-
-
-
合并：将排好序的子序列合并成有序的序列。首先将
[4, 3]和[7]合并成[3, 4, 7]，然后将[1]和[5]合并成[1, 5]，最后将[3, 4, 7]和[1, 5, 8]合并成[1, 3, 4, 5, 7, 8]。完成排序。
五、总结
归并排序是一种高效稳定的排序算法，时间复杂度为 O(nlogn)，比较适合对大规模数据的排序。在实际应用中，由于归并排序需要合并两个有序的子序列，所以需要额外的存储空间来存储这些子序列。