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)