在上一节中讲解了归并排序的递归版《4.比较排序之归并排序(递归)》,通常来讲,递归版的归并排序要更为常用,本节简单介绍下非递归版的归并排序。思路和递归版相同,均为先分解后合并,非递归的重点在于如何确定并合理的分解待排序数组。 对于递归我们是这么做的:
对于非递归来讲,切分的不向递归从大到小,非递归实际上从一开始构建算法的时候都从小到大。
第一次切分排序就确定最小单位为1个数字,将2个数字组合为一组。
第二次切分排序确定为2个数字,将4个数字组合为一组。
第三次切分排序确定为4个数字,将8(7)个数字组合为一组。
也就是说非递归归并排序中分解的依据为:从切分的水长度为1开始,一次归并变回原来的2倍。每完成一次归并则 len = len * 2。
Java
1 package com.algorithm.sort.mergenonrecursive;
2
3 import java.util.Arrays;
4
5 /**
6 * 归并排序(非递归)
7 * Created by yulinfeng on 2017/6/24.
8 */
9 public class Merge {
10
11 public static void main(String[] args) {
12 int[] nums = {6, 5, 3, 1, 7, 2, 4};
13 nums = mergeSort(nums);
14 System.out.println(Arrays.toString(nums));
15 }
16
17 /**
18 * 归并排序(非递归)
19 * 从切分的数组长度为1开始,一次归并变回原来长度的2倍
20 * @param nums 待排序数组
21 * @return 排好序的数组
22 */
23 private static int[] mergeSort(int[] nums) {
24 int len = 1;
25 while (len <= nums.length) {
26 for (int i = 0; i + len <= nums.length; i += len * 2) {
27 int low = i, mid = i + len - 1, high = i + 2 * len - 1;
28 if (high > nums.length - 1) {
29 high = nums.length - 1; //整个待排序数组为奇数的情况
30 }
31 merge(nums, low, mid, high);
32 }
33 len *= 2;
34 }
35 return nums;
36 }
37
38 /**
39 * 将切分的数组进行归并排序,同递归版
40 * @param nums 带排序数组
41 * @param low 左边数组第一个元素索引
42 * @param mid 左边数组最后一个元素索引,mid + 1为右边数组第一个元素索引
43 * @param high 右边数组最后一个元素索引
44 */
45 private static void merge(int[] nums, int low, int mid, int high) {
46 int[] tmpArray = new int[nums.length];
47 int rightIndex = mid + 1;
48 int tmpIndex = low;
49 int begin = low;
50 while (low <= mid && rightIndex <= high) {
51 if (nums[low] <= nums[rightIndex]) {
52 tmpArray[tmpIndex++] = nums[low++];
53 } else {
54 tmpArray[tmpIndex++] = nums[rightIndex++];
55 }
56 }
57 while (low <= mid) {
58 tmpArray[tmpIndex++] = nums[low++];
59 }
60 while (rightIndex <= high) {
61 tmpArray[tmpIndex++] = nums[rightIndex++];
62 }
63 while (begin <= high) {
64 nums[begin] = tmpArray[begin++];
65 }
66 }
67 }