如何在Java与Python实现一个归并排序算法?针对这个问题,这篇文章详细介绍了相对应的分析和解答,希望可以帮助更多想解决这个问题的小伙伴找到更简单易行的方法。
归并排序里运用到算法里很重要的一个思想——分治法:将原问题分解为几个规模较小但类似于原问题的子问题
在每一层递归中都有3个步骤:
1.分解问题
2.解决问题
3.合并问题的解
举例待排序数组:{6, 5, 3, 1, 7, 2, 4},将它原始序列做分解。
可以经过不断的递归分解可以看到已经把原始数组序列不断分解为最小单位,接下来不妨将它们看做是二叉树的叶子节点。
将他们进行两两归并排序形成二叉树(也称为2路归并算法),可见二叉树的根节点即为最终序列。在这个过程中我们完成了剩余的两个步骤:解决问题和合并问题。
理论很简单,实践很“复杂”。对于归并排序的理论从上面的二叉树就看的很明白,将原始待排序数组不断分解最后看成是二叉树的叶子节点,再把它们两两排形成新的节点,逐渐归并为一个节点,此时的节点即为排好序的数组序列。
Java
package com.algorithm.sort.merge;
import java.util.Arrays;
/**
* 归并排序(递归)
* Created by yulinfeng on 2017/6/23.
*/
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));
}
/**
* 归并排序
* @param nums 待排序数组序列
* @return 排好序的数组序列
*/
private static int[] mergeSort(int[] nums) {
segment(nums, 0, nums.length - 1);
return nums;
}
/**
* 递归切分待排
* @param nums 待切分数组
* @param left 待切分最后第一个元素的索引
* @param right 待切分数组最后一个元素的索引
*/
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);
}
/**
* 两两归并排好序的数组(2路归并)
* @param nums 带排序数组对象
* @param left 左边数组的第一个索引
* @param center 左数组的最后一个索引,center + 1右数组的第一个索引
* @param 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++];
}
}
}
Python3
#二路归并排序(递归)
def merge_sort(nums):
segment(nums, 0, len(nums) - 1)
return nums
#切分待排序数组
def segment(nums, left, right):
if left >= right:
return
center = int((left + right) / 2)
segment(nums, left, center)
segment(nums, center + 1, right)
merge(nums, left, center, right)
#两两归并排好序的数组(二路归并)
def merge(nums, left, center, right):
tmpArray = [0] * len(nums)
rightIndex = center + 1 #右数组的第一个元素索引
tmpIndex = left
begin = left
while left <= center and rightIndex <= right:
if nums[left] <= nums[rightIndex]:
tmpArray[tmpIndex] = nums[left]
tmpIndex += 1
left += 1
else:
tmpArray[tmpIndex] = nums[rightIndex]
tmpIndex += 1
rightIndex += 1
while left <= center:
tmpArray[tmpIndex] = nums[left]
tmpIndex += 1
left += 1
while rightIndex <= right:
tmpArray[tmpIndex] = nums[rightIndex]
tmpIndex += 1
rightIndex += 1
while begin <= right:
nums[begin] = tmpArray[begin]
begin += 1
nums = [6, 5, 3, 1, 7, 2, 4]
nums = merge_sort(nums)
print(nums)
关于如何在Java与Python实现一个归并排序算法问题的解答就分享到这里了,希望以上内容可以对大家有一定的帮助,如果你还有很多疑惑没有解开,可以关注亿速云行业资讯频道了解更多相关知识。
亿速云「云服务器」,即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘,价格低至29元/月。点击查看>>
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。