溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
如何在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實現一個歸并排序算法問題的解答就分享到這里了，希望以上內容可以對大家有一定的幫助，如果你還有很多疑惑沒有解開，可以關注億速云行業資訊頻道了解更多相關知識。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
