Beispiel-Tutorial für Vergleichssortierung und Zusammenführungssortierung (rekursiv)

Eine sehr wichtige Idee, die im Merge-Sort-Algorithmus verwendet wird – die Divide-and-Conquer-Methode: Zerlegen Sie das ursprüngliche Problem in mehrere kleinere, aber ähnliche Unterprobleme – „Einführung in Algorithmen“. In jeder Rekursionsebene gibt es 3 Schritte:

1. Zerlegungsproblem
2. Lösen des Problems
3. Lösung des Zusammenführungsproblems
Beispiel für ein zu sortierendes Array: {6 , 5 , 3, 1, 7, 2, 4}, zerlegen Sie seine ursprüngliche Sequenz.

Durch kontinuierliche rekursive Zerlegung können Sie erkennen, dass die ursprüngliche Array-Sequenz kontinuierlich in die kleinsten Einheiten zerlegt wurde. Als nächstes können Sie sie genauso gut als Blattknoten einer Binärdatei betrachten Baum.

　　

Führen Sie sie paarweise zusammen und sortieren Sie sie, um einen Binärbaum zu bilden (auch als 2-Wege-Zusammenführungsalgorithmus bezeichnet). die letzte Sequenz. In diesem Prozess erledigen wir die verbleibenden zwei Schritte: Problemlösung und Zusammenführung.

Die Theorie ist sehr einfach, aber die Praxis ist sehr „komplex“. Die Theorie der Zusammenführungssortierung geht aus dem obigen Binärbaum sehr deutlich hervor. Das zu sortierende ursprüngliche Array wird kontinuierlich zerlegt und schließlich als Blattknoten des Binärbaums betrachtet. Anschließend werden sie zu zweit angeordnet, um neue Knoten zu bilden, und nach und nach zusammengeführt Zu diesem Zeitpunkt sind die Knoten die sortierten Array-Sequenzen.

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)

Das obige ist der detaillierte Inhalt vonBeispiel-Tutorial für Vergleichssortierung und Zusammenführungssortierung (rekursiv). Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!