归并排序java非递归
时间: 2023-09-10 18:11:15 浏览: 53
归并排序是一种经典的排序算法,它的递归实现比较简单,但非递归实现也是相对容易的。下面是Java实现归并排序的非递归版本:
```java
public static void mergeSort(int[] arr) {
int len = arr.length;
int[] result = new int[len];
int block, start;
for (block = 1; block < len * 2; block *= 2) {
for (start = 0; start < len; start += 2 * block) {
int low = start;
int mid = Math.min(start + block, len);
int high = Math.min(start + 2 * block, len);
int start1 = low, end1 = mid;
int start2 = mid, end2 = high;
while (start1 < end1 && start2 < end2) {
result[low++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++];
}
while (start1 < end1) {
result[low++] = arr[start1++];
}
while (start2 < end2) {
result[low++] = arr[start2++];
}
}
int[] temp = arr;
arr = result;
result = temp;
}
if (arr != result) {
System.arraycopy(arr, 0, result, 0, len);
}
}
```
在非递归实现中,我们使用一个数组`result`来保存排序后的结果,然后在每一轮归并时,从前往后依次对相邻的两个子序列进行归并,直到整个数组有序为止。在每一轮归并完成后,我们需要将原数组和临时数组`result`交换一下,以便下一轮继续排序。最后,如果原始数组和临时数组不是同一个数组,我们需要将排序后的结果复制回原数组中。