归并排序非递归 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` 方法用于归并两个子数组。

希望这个示例代码能够帮助你理解归并排序的非递归实现。如有疑问，请随时提出。