如何在Java与Python实现一个归并排序算法?针对这个问题,这篇文章详细介绍了相对应的分析和解答,希望可以帮助更多想解决这个问题的小伙伴找到更简单易行的方法。
归并排序里运用到算法里很重要的一个思想——分治法:将原问题分解为几个规模较小但类似于原问题的子问题
在每一层递归中都有3个步骤:
分解问题
解决问题
合并问题的解
举例待排序数组:{6, 5, 3, 1, 7, 2, 4},将它原始序列做分解。
可以经过不断的递归分解可以看到已经把原始数组序列不断分解为最小单位,接下来不妨将它们看做是二叉树的叶子节点。
将他们进行两两归并排序形成二叉树(也称为2路归并算法),可见二叉树的根节点即为最终序列。在这个过程中我们完成了剩余的两个步骤:解决问题和合并问题。
理论很简单,实践很“复杂”。对于归并排序的理论从上面的二叉树就看的很明白,将原始待排序数组不断分解最后看成是二叉树的叶子节点,再把它们两两排形成新的节点,逐渐归并为一个节点,此时的节点即为排好序的数组序列。
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
软考中级精品资料免费领
- 历年真题答案解析
- 备考技巧名师总结
- 高频考点精准押题
- 资料下载
- 历年真题
193.9 KB下载数265
191.63 KB下载数245
143.91 KB下载数1148
183.71 KB下载数642
644.84 KB下载数2756