归并排序是一种分治算法,其基本思想是将数组分成两部分,分别进行排序,然后将结果合并。这种算法是分治法的典型应用。下面的Java代码实现了归并排序,包括递归和非递归两种方式。
代码解读
递归方法实现
public static void mergeSort1(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
process(arr, 0, arr.length - 1);
}
递归方法 mergeSort1
首先检查输入数组 arr
是否为空或长度小于2,若是则直接返回。然后调用 process
方法对数组进行排序。
public static void process(int[] arr, int L, int R) {
if (L == R) { // base case
return;
}
int mid = L + ((R - L) >> 1);
process(arr, L, mid);
process(arr, mid + 1, R);
merge(arr, L, mid, R);
}
process
方法是递归排序的核心,它将数组从中间分成两部分,然后对每一部分分别调用 process
方法进行排序,最后调用 merge
方法将两部分合并。
非递归方法实现
public static void mergeSort2(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
int N = arr.length;
int mergeSize = 1;
while (mergeSize < N) {
int L = 0;
while (L < N) {
if (mergeSize >= N - L) {
break;
}
int M = L + mergeSize - 1;
int R = M + Math.min(mergeSize, N - M - 1);
merge(arr, L, M, R);
L = R + 1;
}
if (mergeSize > N / 2) {
break;
}
mergeSize <<= 1;
}
}
非递归方法 mergeSort2
的实现思路是通过一个外部循环控制合并的大小 mergeSize
,然后在内部循环中对数组进行分组和合并。
合并代码
private static void merge(int[] arr, int l, int m, int r) {
// 生成一个临时数组
int[] help = new int[r - l + 1];
int i = 0;//记录数组元素
int p1 = l;//左组指针
int p2 = m + 1;//右组指针
//while循环规定指针的界限
while (p1 <= m && p2 <= r) {
help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
}
while (p1 <= m) {
//左组有剩余元素,不包括生成的临时组,直接将其加入
help[i++] = arr[p1++];
}
while (p2 <= r) {
help[i++] = arr[p2++];
}
}
这段代码是归并排序中的合并部分,它的作用是将两个已经有序的子数组合并成一个有序的数组。其中,参数arr是待排序的数组,参数l、m、r分别是代表数组左、中、右三个位置的下标。首先,代码创建了一个临时数组help,表示辅助排序的数组,它的长度就是左右两个子数组需要合并的元素个数。然后,代码定义了一个指针i,用于记录help数组中元素的下标。接着,定义了两个指针p1、p2,分别表示左、右两个子数组的起始位置。这里使用while循环来遍历两个子数组的元素,并将其依次放入辅助数组help中。判断当前左右两个数组中哪个元素更小,就将其放入help数组中,并让相应的指针向右移动。当遍历完其中一个子数组后,如果另一个子数组还有剩余的元素,那么将这些元素直接放入help数组中即可。最后,在合并完成后,需要将help数组中排好序的元素复制回原数组arr对应的位置。
测试
public static void main(String[] args) {
int testTime = 500000;
int maxSize = 100;
int maxValue = 100;
System.out.println("测试开始");
for (int i = 0; i < testTime; i++) {
int[] arr1 = generateRandomArray(maxSize, maxValue);
int[] arr2 = copyArray(arr1);
mergeSort1(arr1);
mergeSort2(arr2);
if (!isEqual(arr1, arr2)) {
System.out.println("出错了!");
printArray(arr1);
printArray(arr2);
break;
}
}
System.out.println("测试结束");
}
在 main
方法中,我们进行了大量的测试,包括生成随机数组,复制数组,然后使用两种方法进行排序,并检查排序结果是否相等。文章来源:https://www.toymoban.com/news/detail-565741.html
总结
归并排序是一种非常高效的排序算法,其时间复杂度是O(nlogn),空间复杂度是O(n),它是一种稳定的排序算法。以上就是Java实现归并排序的全部内容,希望对大家有所帮助。文章来源地址https://www.toymoban.com/news/detail-565741.html
到了这里,关于Java实现归并排序的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!