比較ソートとマージソート（再帰）のサンプルチュートリアル

マージソートで使用されるアルゴリズムで非常に重要な考え方 - 分割統治法: 元の問題をいくつかの小さいが類似したサブ問題に分解する - 「アルゴリズム入門」。再帰の各レベルには 3 つのステップがあります:

1. 問題を分解する
2. 問題を解決する
3. 問題の解決策を結合する
ソートされる配列の例: {6, 5, 3, 1, 7, 2, 4 }、元のシーケンスを分解します。

連続再帰分解を通して、元の配列シーケンスが最小単位に連続的に分解されていることがわかります。次に、それらをバイナリ ツリーの葉ノードとみなすこともできます。

それらをペアでマージおよびソートしてバイナリツリーを形成します（2方向マージアルゴリズムとも呼ばれます）。バイナリツリーのルートノードが最終シーケンスであることがわかります。このプロセスでは、残りの 2 つのステップ (問題解決とマージ) を完了します。

理論はとてもシンプルですが、実践はとても「複雑」です。マージ ソートの理論は、上記のバイナリ ツリーから非常に明らかです。ソートされる元の配列は継続的に分解され、最終的にバイナリ ツリーの葉ノードとみなされ、その後、それらが 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 中国語 Web サイトの他の関連記事を参照してください。