专栏首页余林丰5.比较排序之归并排序(非递归)

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 条评论
登录 后参与评论

相关文章

  • 2.比较排序之梳排序

      梳排序的知名度远没有其他排序算法那么高,它是在冒泡排序的基础上做的改进,引入类似“步长”以及“子序列”概念,这两个概念在后面的排序算法中会经常提及。   待...

    用户1148394
  • 1.比较排序之冒泡排序

      冒泡排序可以说是在排序算法中最为入门级别的算法之一了。因为其简单易于理解,常在课堂中作为排序的入门算法。   冒泡排序见名生意,其排序过程如同水里的泡一般由...

    用户1148394
  • 【好书推荐】《剑指Offer》之硬技能(编程题12~16)

    题目:请设计一个函数,用来判断一个矩阵中是否存在一条包含其字符串所有字符的路径。路径可以从矩阵中的任意一格开始,每一步可以在矩阵中向左、右、上、下移动一格。如果...

    用户1148394
  • 【LeetCode】找出数组中重复的数字day01

    居士
  • LeetCode 189. 旋转数组(环形替换)

    来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/rotate-array 著作权归领扣网络所有。商业...

    Michael阿明
  • LeetCode 217. Contains Duplicate

    ShenduCC
  • No.015 3Sum

    15. 3Sum Total Accepted: 131800 Total Submissions: 675028 Difficulty: Medium   G...

    mukekeheart
  • 你必须知道的指针基础-8.栈空间与堆空间

    一个由C/C++编译的程序占用的内存分为以下几个部分:  1、栈区(stack):又编译器自动分配释放,存放函数的参数值,局部变量的值等,其操作方式类似于...

    Edison Zhou
  • 每日算法系列【LeetCode 719】找出第 k 小的距离对

    给定一个整数数组,返回所有数对之间的第 k 个最小距离。一对 (A, B) 的距离被定义为 A 和 B 之间的绝对差值。

    godweiyang
  • 【LeetCode两题选手】算法类题目(7.27)

    回溯法 :一种通过探索所有可能的候选解来找出所有的解的算法。如果候选解被确认不是一个解的话(或者至少不是最后一个解),回溯算法会通过在上一步进行一些变化抛弃该解...

    看、未来

扫码关注云+社区

领取腾讯云代金券