C# 병합 정렬

C# 병합 정렬

using System;  
using System.Collections.Generic;  
using System.Linq;  
using System.Text;  
namespace Sort  
{  
    class MergeSorter  
    {  
        /// <summary>  
        /// 归并排序之归：归并排序入口   
        /// </summary>  
        /// <param name="data">无序数组</param>  
        /// <returns>有序数组</returns>  
         public static int[] Sort(int[] data)  
        {  
            //若data为null，或只剩下1 or 0个元素，返回，不排序  
            if (null == data || data.Length <= 1)  
            {  
                return data;  
            }  
            //取数组中间下标  
            int middle = data.Length >> 1;  
            //初始化临时数组let,right，并定义result作为最终有序数组，若数组元素奇数个，将把多余的那元素空间预留在right临时数组  
            int[] left = new int[middle];  
            int[] right =  new int[data.Length - middle];  
            int[] result = new int[data.Length];  
            for (int i = 0; i < data.Length; i++)  
            {  
                if (i < middle)  
                {  
                    left[i] = data[i];  
                }  
                else  
                {  
                    right[i-middle] = data[i]; //此处i-middle，让我省掉定义一个j，性能有所提高  
                }  
            }  
            left = Sort(left);//递归左数组  
            right = Sort(right);//递归右数组  
            result = Merge(left, right);//开始排序  
            return result;  
        }  
        /// <summary>  
        /// 归并排序之并:排序在这一步  
        /// </summary>  
        /// <param name="a">左数组</param>  
        /// <param name="b">右数组</param>  
        /// <returns>合并左右数组排序后返回</returns>  
         private static int[] Merge(int[] a, int[] b)  
         {  
            //定义结果数组，用来存储最终结果  
            int[] result = new int[a.Length + b.Length];  
            int i = 0, j = 0, k = 0;  
            while (i < a.Length && j < b.Length)  
            {  
                if (a[i] < b[j])//左数组中元素小于右数组中元素  
                {  
                    result[k++] = a[i++];//将小的那个放到结果数组  
                }  
                else//左数组中元素大于右数组中元素  
                {  
                    result[k++] = b[j++];//将小的那个放到结果数组  
                }  
            }  
            while (i < a.Length)//这里其实是还有左元素，但没有右元素   
            {  
                result[k++] = a[i++];  
            }  
            while (j < b.Length)//有右元素，无左元素  
            {  
                result[k++] = b[j++];  
            }  
            return result;//返回结果数组  
        }  
    }  
}

병합 정렬:
병합 정렬 방법은 두 개 이상의 순서 목록을 새로운 순서 목록으로 병합하는 것입니다. 즉, 정렬된 시퀀스는 여러 하위 시퀀스로 나뉩니다. , 각 하위 시퀀스는 순서가 지정됩니다. 그런 다음 정렬된 하위 시퀀스를 전체 정렬된 시퀀스에 병합합니다. 이 알고리즘은 분할 정복(Divide and Conquer) 방식을 사용하는 매우 일반적인 응용 프로그램입니다.

순서가 지정된 하위 시퀀스를 병합하여 완전히 정렬된 시퀀스를 얻습니다. 즉, 먼저 각 하위 시퀀스를 정렬한 다음 하위 시퀀스 세그먼트를 정렬합니다. 두 개의 순서 목록이 하나의 순서 목록으로 병합되는 경우 이를 양방향 병합이라고 합니다.

정렬되지 않은 시퀀스가 ​​있다고 가정하면 먼저 분할 방법을 사용하여 시퀀스를 정렬된 하위 시퀀스로 나눈 다음 병합 방법을 사용하여 하위 시퀀스를 하나씩 분리합니다. 분할 및 병합 과정은 아래 범례에서 볼 수 있습니다.

위 그림에서 알 수 있듯이 먼저 정렬되지 않은 시퀀스를 가운데부터 2부분으로 나눈 다음, 2개 부분으로 4개 부분으로 나누고, 하나씩 데이터로 분할될 때까지 순서대로 나누고, 이 데이터들을 합쳐서 순서대로 만들고, 계속 병합하여 최종적으로 순서가 있는 순서가 됩니다.

두 개의 정렬된 하위 시퀀스를 하나의 정렬된 시퀀스로 병합하는 방법은 무엇입니까? 아래 방법을 참고하시면 됩니다.

두 개의 정렬된 하위 시퀀스가 ​​있다고 가정합니다.

시퀀스 A: 1 23 34 65

시퀀스 B: 2 13 14 87

그런 다음 아래 단계에 따라 하나의 시퀀스로 병합할 수 있습니다.

(1) 먼저 새로운 시퀀스 C[8]을 설정합니다.
(2) A[0]과 B[0]을 비교하고, A[0] = 1, B[0] = 2, A[0] < B[0], 그러면 C[0] = 1
(3) A[1]과 B[0]을 비교하면 A[1] = 23, B[0] = 2, A[1] > B[0], 그러면 C[1] = 2
(4) A[1]과 B[1]을 비교하면 A[1] = 23, B[1] = 13, A[1] > B[1]이면 C[2] = 13
(5) A[1]과 B[2]를 비교하면 A[1] = 23, B[2] = 14, A[1] > B[2]이면 C[3] = 14
6) A[1]과 B[3]을 비교하면 A[1] = 23, B[3] = 87, A[1] (7 ) A[2]와 B[3]을 비교하면 A[2] = 34, B[3] = 87, A[2] (8) A[3]과 B[3]을 비교하면 A[3] = 65, B[3] = 87, A[3] (9) 마지막으로; B[3]을 C에 복사한 다음 C[7] = 87을 복사합니다. 병합이 완료되었습니다.

C# 시프트 연산(왼쪽 시프트 및 오른쪽 시프트)

병합 정렬, 시간 복잡도는 O(nlogn)입니다.

병합 정렬의 효율성은 상대적으로 높습니다. 시퀀스의 길이가 N이라고 가정합니다. 각 단계는 순서가 지정된 시퀀스를 병합하는 프로세스입니다. O(N)으로 기록되므로 합계는 O(N*logN)입니다. 병합 정렬은 매번 인접한 데이터에 대해 작동하기 때문에 O(N*logN)의 여러 병합 정렬(빠른 정렬, 병합 정렬, 힐 정렬, 힙 정렬)도 상대적으로 효율적입니다.

위 내용은 C# 병합정렬 내용입니다. 더 많은 관련 내용은 PHP 중국어 홈페이지(www.php.cn)를 참고해주세요!