文章详情

短信预约-IT技能 免费直播动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

如何在Java与Python实现一个归并排序算法

2023-05-31 12:06

关注

如何在Java与Python实现一个归并排序算法?针对这个问题,这篇文章详细介绍了相对应的分析和解答,希望可以帮助更多想解决这个问题的小伙伴找到更简单易行的方法。

归并排序里运用到算法里很重要的一个思想——分治法:将原问题分解为几个规模较小但类似于原问题的子问题

在每一层递归中都有3个步骤:

分解问题

解决问题

合并问题的解

举例待排序数组:{6, 5, 3, 1, 7, 2, 4},将它原始序列做分解。

如何在Java与Python实现一个归并排序算法

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

  如何在Java与Python实现一个归并排序算法  

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

如何在Java与Python实现一个归并排序算法

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

Java

package com.algorithm.sort.merge;import java.util.Arrays;public class Merge {  public static void main(String[] args) {    int[] nums = {6, 5, 3, 1, 7, 2, 4};    nums = mergeSort(nums);    System.out.println(Arrays.toString(nums));  }    private static int[] mergeSort(int[] nums) {    segment(nums, 0, nums.length - 1);    return nums;  }    private static void segment(int[] nums, int left, int right) {    if (left >= right)      return;    // 找出中间索引    int center = (left + right) / 2;    // 对左边数组进行递归    segment(nums, left, center);    // 对右边数组进行递归    segment(nums, center + 1, right);    // 合并    merge(nums, left, center, right);  }    private static void merge(int[] nums, int left, int center, int right) {    int[] tmpArray = new int[nums.length];    int rightIndex = center + 1;  // 右数组第一个元素索引    int tmpIndex = left;  //临时数组索引    int begin = left;  // 缓存左数组第一个元素的索引,用于将排好序的数组拷贝回原数组    while (left <= center && rightIndex <= right) {      if (nums[left] <= nums[rightIndex]) {        tmpArray[tmpIndex++] = nums[left++];      } else {        tmpArray[tmpIndex++] = nums[rightIndex++];      }    }    while (left <= center) {      tmpArray[tmpIndex++] = nums[left++];    }    while (rightIndex <= right) {      tmpArray[tmpIndex++] = nums[rightIndex++];    }    while (begin <= right) {      nums[begin] = tmpArray[begin++];    }  }}

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 资料下载
  • 历年真题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯