比較排序之歸併排序（遞歸）的實例教程

　　歸併排序裡運用到演算法裡很重要的一個想法－分治法：將原問題分解為幾個規模較小但類似原問題的子問題－《演算法導論》。在每一層遞迴中都有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         return10     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 = left20     begin = left21     while left <= center and rightIndex <= right:22         if nums[left] <= nums[rightIndex]:23             tmpArray[tmpIndex] = nums[left]24             tmpIndex += 125             left += 126         else:27             tmpArray[tmpIndex] = nums[rightIndex]28             tmpIndex += 129             rightIndex += 130     while left <= center:31         tmpArray[tmpIndex] = nums[left]32         tmpIndex += 133         left += 134     while rightIndex <= right:35         tmpArray[tmpIndex] = nums[rightIndex]36         tmpIndex += 137         rightIndex += 138     while begin <= right:39         nums[begin] = tmpArray[begin]40         begin += 141 42 nums = [6, 5, 3, 1, 7, 2, 4]43 nums = merge_sort(nums)44 print(nums)

 

#

以上是比較排序之歸併排序（遞歸）的實例教程的詳細內容。更多資訊請關注PHP中文網其他相關文章！