归并排序非递归 java
时间: 2023-09-10 20:11:52 浏览: 115
归并排序是一种基于分治思想的排序算法。非递归实现的归并排序可以通过迭代来完成。下面是一个使用 Java 实现的归并排序非递归版本的示例代码:
```java
public class MergeSort {
public static void mergeSort(int[] arr) {
if (arr == null || arr.length <= 1) {
return;
}
int n = arr.length;
int[] temp = new int[n];
int size = 1; // 子数组的大小,初始为1
while (size < n) {
mergePass(arr, temp, size, n); // 执行一趟归并排序
size *= 2; // 子数组大小翻倍
}
}
private static void mergePass(int[] arr, int[] temp, int size, int n) {
int i = 0;
while (i + 2 * size <= n) {
merge(arr, temp, i, i + size - 1, i + 2 * size - 1); // 归并相邻的两个子数组
i += 2 * size;
}
if (i + size < n) {
merge(arr, temp, i, i + size - 1, n - 1); // 归并剩余的两个子数组
}
}
private static void merge(int[] arr, int[] temp, int left, int mid, int right) {
int i = left; // 左边子数组的起始位置
int j = mid + 1; // 右边子数组的起始位置
int k = left; // 归并后数组的起始位置
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 m = left; m <= right; m++) {
arr[m] = temp[m];
}
}
public static void main(String[] args) {
int[] arr = {5, 2, 8, 4, 9, 1};
System.out.println("Before sorting:");
for (int num : arr) {
System.out.print(num + " ");
}
mergeSort(arr);
System.out.println("\nAfter sorting:");
for (int num : arr) {
System.out.print(num + " ");
}
}
}
```
这个示例代码中,`mergeSort` 方法用于调用非递归归并排序算法。`mergePass` 方法用于执行一趟归并排序,`merge` 方法用于归并两个子数组。
希望这个示例代码能够帮助你理解归并排序的非递归实现。如有疑问,请随时提出。
阅读全文