비교 정렬 및 병합 정렬(재귀) 튜토리얼 예제

　병합 정렬에 사용되는 알고리즘의 매우 중요한 아이디어 - 분할 및 정복 방법: 원래 문제를 더 작지만 유사한 여러 하위 문제로 분해 - "알고리즘 소개". 각 재귀 수준에는 3단계가 있습니다:

　1. 문제 분해
　2. 문제 해결
　3. 문제 풀이 결합
　 정렬할 배열의 예: {6, 5, 3, 1, 7, 2, 4 }, 원래 시퀀스를 분해합니다.

연속 재귀 분해를 통해 원래 배열 시퀀스가 ​​가장 작은 단위로 연속적으로 분해되었음을 확인할 수 있습니다. 다음으로는 이진 트리의 리프 노드로 간주해도 됩니다.

　　　　

　 쌍으로 병합하고 정렬하여 이진 트리를 형성합니다(양방향 병합 알고리즘이라고도 함). 이진 트리의 루트 노드가 최종 시퀀스임을 알 수 있습니다. 이 프로세스에서 우리는 문제 해결과 문제 병합이라는 나머지 두 단계를 완료합니다.

　이론은 매우 간단하지만 실천은 매우 "복잡"합니다. 병합 정렬의 이론은 위의 이진 트리에서 매우 명확합니다. 정렬할 원래 배열은 지속적으로 분해되어 최종적으로 이진 트리의 리프 노드로 간주된 다음 두 개로 배열되어 새로운 노드를 형성하고 점차적으로 병합됩니다. 이때 노드는 정렬된 배열 시퀀스입니다.

　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 중국어 웹사이트의 기타 관련 기사를 참조하세요!