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

4.比较排序之归并排序(递归)

  归并排序里运用到算法里很重要的一个思想——分治法:将原问题分解为几个规模较小但类似于原问题的子问题——《算法导论》。在每一层递归中都有3个步骤:

  1.分解问题   2.解决问题   3.合并问题的解   举例待排序数组:{6, 5, 3, 1, 7, 2, 4},将它原始序列做分解。

  可以经过不断的递归分解可以看到已经把原始数组序列不断分解为最小单位,接下来不妨将它们看做是二叉树的叶子节点。

  将他们进行两两归并排序形成二叉树(也称为2路归并算法),可见二叉树的根节点即为最终序列。在这个过程中我们完成了剩余的两个步骤:解决问题和合并问题。

  理论很简单,实践很“复杂”。对于归并排序的理论从上面的二叉树就看的很明白,将原始待排序数组不断分解最后看成是二叉树的叶子节点,再把它们两两排形成新的节点,逐渐归并为一个节点,此时的节点即为排好序的数组序列。

  Java

 1 package com.algorithm.sort.merge;
 2 
 3 import java.util.Arrays;
 4 
 5 /**
 6  * 归并排序(递归)
 7  * Created by yulinfeng on 2017/6/23.
 8  */
 9 public class Merge {
10     public static void main(String[] args) {
11         int[] nums = {6, 5, 3, 1, 7, 2, 4};
12         nums = mergeSort(nums);
13         System.out.println(Arrays.toString(nums));
14     }
15 
16     /**
17      * 归并排序
18      * @param nums 待排序数组序列
19      * @return 排好序的数组序列
20      */
21     private static int[] mergeSort(int[] nums) {
22         segment(nums, 0, nums.length - 1);
23         return nums;
24     }
25 
26     /**
27      * 递归切分待排
28      * @param nums 待切分数组
29      * @param left 待切分最后第一个元素的索引
30      * @param right 待切分数组最后一个元素的索引
31      */
32     private static void segment(int[] nums, int left, int right) {
33         if (left >= right)
34             return;
35         // 找出中间索引
36         int center = (left + right) / 2;
37         // 对左边数组进行递归
38         segment(nums, left, center);
39         // 对右边数组进行递归
40         segment(nums, center + 1, right);
41         // 合并
42         merge(nums, left, center, right);
43     }
44 
45     /**
46      * 两两归并排好序的数组(2路归并)
47      * @param nums 带排序数组对象
48      * @param left 左边数组的第一个索引
49      * @param center 左数组的最后一个索引,center + 1右数组的第一个索引
50      * @param right 右数组的最后一个索引
51      */
52     private static void merge(int[] nums, int left, int center, int right) {
53         int[] tmpArray = new int[nums.length];
54         int rightIndex = center + 1;   // 右数组第一个元素索引
55         int tmpIndex = left;    //临时数组索引
56         int begin = left;   // 缓存左数组第一个元素的索引,用于将排好序的数组拷贝回原数组
57         while (left <= center && rightIndex <= right) {
58             if (nums[left] <= nums[rightIndex]) {
59                 tmpArray[tmpIndex++] = nums[left++];
60             } else {
61                 tmpArray[tmpIndex++] = nums[rightIndex++];
62             }
63         }
64         while (left <= center) {
65             tmpArray[tmpIndex++] = nums[left++];
66         }
67         while (rightIndex <= right) {
68             tmpArray[tmpIndex++] = nums[rightIndex++];
69         }
70         while (begin <= right) {
71             nums[begin] = tmpArray[begin++];
72         }
73     }
74 }

Python3

 1 #二路归并排序(递归)
 2 def merge_sort(nums):
 3     segment(nums, 0, len(nums) - 1)
 4     return nums
 5 
 6 #切分待排序数组
 7 def segment(nums, left, right):
 8     if left >= right:
 9         return
10     center = int((left + right) / 2)
11     segment(nums, left, center)
12     segment(nums, center + 1, right)
13     merge(nums, left, center, right)
14 
15 #两两归并排好序的数组(二路归并)
16 def merge(nums, left, center, right):
17     tmpArray = [0] * len(nums)
18     rightIndex = center + 1     #右数组的第一个元素索引
19     tmpIndex = left
20     begin = left
21     while left <= center and rightIndex <= right:
22         if nums[left] <= nums[rightIndex]:
23             tmpArray[tmpIndex] = nums[left]
24             tmpIndex += 1
25             left += 1
26         else:
27             tmpArray[tmpIndex] = nums[rightIndex]
28             tmpIndex += 1
29             rightIndex += 1
30     while left <= center:
31         tmpArray[tmpIndex] = nums[left]
32         tmpIndex += 1
33         left += 1
34     while rightIndex <= right:
35         tmpArray[tmpIndex] = nums[rightIndex]
36         tmpIndex += 1
37         rightIndex += 1
38     while begin <= right:
39         nums[begin] = tmpArray[begin]
40         begin += 1
41 
42 nums = [6, 5, 3, 1, 7, 2, 4]
43 nums = merge_sort(nums)
44 print(nums)

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • JAVA学习Swing绝对局部简单学习

    package com.swing; import java.awt.Container; import javax.swing.JButton; impo...

    别先生
  • Es6浅析

    Es6浅析 Babel 是一个 JavaScript编译器,它可以把我们编写的符合 ECMAScript 6 标准的代码完美地转换为 ECMAScript 5 ...

    IMWeb前端团队
  • Java抽象类与接口的区别

    很多常见的面试题都会出诸如抽象类和接口有什么区别,什么情况下会使用抽象类和什么情况你会使用接口这样的问题。本文我们将仔细讨论这些话题。

    Java后端工程师
  • JavaScript强化教程——AngularJS 指令

    本文为 H5EDU 机构官方 HTML5培训 AngularJS 通过被称为 指令 的新属性来扩展 HTML。 AngularJS 通过内置的指令来为应用添加功...

    IMWeb前端团队
  • JAVA学习Swing章节按钮组件JButton的简单学习

    package com.swing; import java.awt.Container; import java.awt.Dimension; import...

    别先生
  • JAVA学习AWT绘图

    package com.graphics; import java.awt.Graphics; import javax.swing.JFrame; imp...

    别先生
  • jQuery/javascript实现简单网页计算器

    1 <html> 2 <head> 3 <meta charset="utf-8"> 4 <title>jQuery实现</title> 5 <scr...

    别先生
  • Nativescript跨终端应用程序开发方案研究

    1.环境准备 安装nodejs 安装nativescript $npm install -g nativescript 或者下载github上项目代码进行构建(...

    IMWeb前端团队
  • Java攻城狮面试考题

    1 <html> 2 <head> 3 <meta http-equiv="Content-Type" content="text/html; chars...

    别先生
  • JAVA学习绘图颜色及其笔画属性设置字体显示文字

    package com.graphics; import java.awt.*; import java.awt.geom.Rectangle2D; impo...

    别先生

扫码关注云+社区

领取腾讯云代金券