归并排序java非递归
时间: 2023-09-10 17:10:46 浏览: 53
归并排序的非递归实现需要借助栈来完成,以下是Java代码示例:
```java
public static void mergeSort(int[] arr) {
int n = arr.length;
int[] tmp = new int[n];
int step = 1;
while (step < n) {
int start = 0;
while (start < n) {
int mid = start + step;
if (mid >= n) {
break;
}
int end = Math.min(start + 2 * step, n);
merge(arr, tmp, start, mid, end);
start += 2 * step;
}
step *= 2;
}
}
private static void merge(int[] arr, int[] tmp, int start, int mid, int end) {
int i = start, j = mid, k = start;
while (i < mid && j < end) {
if (arr[i] < arr[j]) {
tmp[k++] = arr[i++];
} else {
tmp[k++] = arr[j++];
}
}
while (i < mid) {
tmp[k++] = arr[i++];
}
while (j < end) {
tmp[k++] = arr[j++];
}
for (i = start; i < end; i++) {
arr[i] = tmp[i];
}
}
```
首先定义了一个step变量,表示步长,初始值为1,每次循环乘以2,直到大于等于数组长度。
在每次循环中,从数组的起始位置开始,每隔step个元素一组,进行归并排序操作。归并排序的具体实现可以参考递归版本的代码。
需要注意的是,在非递归实现中,需要使用一个临时数组tmp来存储归并排序的结果。最后再将tmp中的元素复制回原数组中。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)