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

发布时间:2017-7-1 11:31:21编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"5.比较排序之归并排序(非递归) ",主要涉及到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 }


上一篇:免费的 Vue.js 入门与进阶视频教程
下一篇:编写bat脚本执行msyql建库sql

相关文章

相关评论

本站评论功能暂时取消,后续此功能例行通知。

一、不得利用本站危害国家安全、泄露国家秘密,不得侵犯国家社会集体的和公民的合法权益,不得利用本站制作、复制和传播不法有害信息!

二、互相尊重,对自己的言论和行为负责。

好贷网好贷款