在上一节中讲解了归并排序的递归版《4.比较排序之归并排序（递归）》，通常来讲，递归版的归并排序要更为常用，本节简单介绍下非递归版的归并排序。思路和递归版相同，均为先分解后合并，非递归的重点在于如何确定并合理的分解待排序数组。
对于非递归来讲，切分的不向递归从大到小，非递归实际上从一开始构建算法的时候都从小到大。
第一次切分排序就确定最小单位为1个数字，将2个数字组合为一组。
package com.algorithm.sort.mergenonrecursive;
import java.util.arrays;
/**
* 归并排序（非递归）
* created by yulinfeng on 2017/6/24.
*/
public class merge {
public static void main(string[] args) {
int[] nums = {6, 5, 3, 1, 7, 2, 4};
nums = mergesort(nums);
system.out.println(arrays.tostring(nums));
}
/**
* 归并排序（非递归）
* 从切分的数组长度为1开始，一次归并变回原来长度的2倍
* @param nums 待排序数组
* @return 排好序的数组
*/
private static int[] mergesort(int[] nums) {
int len = 1;
while (len <= nums.length) {
for (int i = 0; i + len <= nums.length; i += len * 2) {
int low = i, mid = i + len - 1, high = i + 2 * len - 1;
if (high > nums.length - 1) {
high = nums.length - 1; //整个待排序数组为奇数的情况
}
merge(nums, low, mid, high);
}
len *= 2;
}
return nums;
}
/**
* 将切分的数组进行归并排序，同递归版
* @param nums 带排序数组
* @param low 左边数组第一个元素索引
* @param mid 左边数组最后一个元素索引，mid + 1为右边数组第一个元素索引
* @param high 右边数组最后一个元素索引
*/
private static void merge(int[] nums, int low, int mid, int high) {
int[] tmparray = new int[nums.length];
int rightindex = mid + 1;
int tmpindex = low;
int begin = low;
while (low <= mid && rightindex <= high) {
if (nums[low] <= nums[rightindex]) {
tmparray[tmpindex++] = nums[low++];
} else {
tmparray[tmpindex++] = nums[rightindex++];
}
}
while (low <= mid) {
tmparray[tmpindex++] = nums[low++];
}
while (rightindex <= high) {
tmparray[tmpindex++] = nums[rightindex++];
}
while (begin <= high) {
nums[begin] = tmparray[begin++];
}
}
}
以上就是java比较排序之归并排序（非递归）实例详解的详细内容。