5.比较排序之归并排序(非递归)

  在上一节中讲解了归并排序的递归版《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 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏深度学习与计算机视觉

算法-从1,...,99,2015这100个数中任意选择若干个数(可能为0个数)求异或,试求异或的期望值

题目: 从1,2,3,…..98,99,2015这100个数中任意选择若干个数(可能为0个数)求异或,试求异或的期望值。 解题思路: 这是阿里巴巴的...

316100
来自专栏深度学习与计算机视觉

算法-合并两个排序的链表

题目: 输入两个递增排序的链表,合并着两个链表并使新链表中的结点仍然是按照递增顺序的。例如输入的链表1和链表2如下,合并后的为链表3。链表的结点定义如下: ...

232100
来自专栏深度学习与计算机视觉

算法-重建二叉树

题目: 输入某二叉树的前序遍历与中序遍历结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果均无重复数字,前序遍历序列为{},中序遍历序列为{},则重...

212100
来自专栏算法与数据结构

PTA 7-1 畅通工程之局部最小花费问题(35 分)

7-1 畅通工程之局部最小花费问题(35 分) 某地区经过对城镇交通状况的调查,得到现有城镇间快速道路的统计数据,并提出“畅通工程”的目标:使整个地区任何两个城...

33370
来自专栏深度学习与计算机视觉

算法-删除字符串中的公共字符

题目: 输入两个字符串,从第一字符串中删除第二个字符串中所有的字符。例如,输入“They are students.”和”aeiou”,则删除之后的第一个字...

27160
来自专栏深度学习与计算机视觉

OpenCV 实现SSIM结构相似性算法

SSIM算法的介绍: http://blog.csdn.net/chaipp0607/article/details/70158835 代码做了一下处理: ...

49970
来自专栏IMWeb前端团队

尾递归的后续探究

0 前言 去年大致也是这个事件,曾经探索过尾调用(PTC)相关的内容,并总结了一片文章——朋友你听说过尾递归吗。同时在文章的最后也留下了一个坑: 尾递归写法的...

247100
来自专栏算法与数据结构

PTA 根据后序和中序遍历输出先序遍历(25 分)

7-1 根据后序和中序遍历输出先序遍历(25 分) 本题要求根据给定的一棵二叉树的后序遍历和中序遍历结果,输出该树的先序遍历结果。 输入格式: 第一行给出正整数...

567100
来自专栏深度学习与计算机视觉

算法-二维数组中的查找

问题: 在一个二维数组中,每一行元素都按照从左到右递增的顺序排序,每一列元素都按照从上到下递增的顺序排序。实现一个查找功能的函数,函数的输入为二维数组和一个...

208100
来自专栏算法与数据结构

PTA 旅游规划(25 分)

7-10 旅游规划(25 分) 有了一张自驾旅游路线图,你会知道城市间的高速公路长度、以及该公路要收取的过路费。现在需要你写一个程序,帮助前来咨询的游客找一条出...

43460

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励