정렬 알고리즘 - 병합 정렬 [코드 포함]

병합 정렬이란 무엇인가요?

　 간단히 말해서 병합 정렬은 순서가 지정된 두 시퀀스를 통합하는 것입니다.

추천 튜토리얼: PHP 비디오 튜토리얼

두 개의 정렬된 시퀀스를 어떻게 통합하나요?

　 그러면 이제 M=｛m1,m2,m3,...,mx｝ 시퀀스와 N=｛n1,n2,n3,...,ny｝ 시퀀스가 ​​있다고 가정합니다. 이미 순서가 지정된 시퀀스입니다. 먼저 빈 시퀀스 K = {}를 만든 다음 m1과 n1을 비교하고 m1

병합 정렬은 정렬된 시퀀스를 통합하므로 정렬되지 않은 시퀀스는 정렬할 수 없다는 뜻 아닌가요?

병합 정렬은 분할 정복 방법을 기반으로 합니다. 즉, 완전히 무질서한 시퀀스를 무선으로 분할하여 정렬된 시퀀스를 얻을 수 있습니다. 예: 이제 M=｛m1, m2, m3 ,... .,mx}, M 시퀀스는 완전히 무질서한 시퀀스입니다. 그러면 M 시퀀스는 여러 개의 작은 시퀀스({m1, m2}, {m3, m4}....{mx- 1, mx})로 나눌 수 있습니다. 이번에는 이러한 시퀀스가 ​​순서대로 정렬되어 있어 병합 작업을 통해 정렬할 수 있습니다. 따라서 병합 정렬은 정렬되지 않은 시퀀스도 정렬할 수 있으며 속도는 안정적인 정렬인 퀵 정렬에 이어 두 번째입니다.

시퀀스를 분할하는 방법은 무엇입니까?

이전 질문이 언급되었습니다. 병합 정렬은 분할 및 정복의 구현이 분할 순서에 반영됩니다. 이제 M=｛m1, m2, m3, .. .., mx}, 첫 번째 나눗셈: M1 = {m1, m2,..., m(x+1)/2}, M2 = {m(x+1)/2 +1, m( x+1 )/2 +2,...,mx}, 첫 번째 분할 후 M1 및 M2 시퀀스를 얻은 다음 M1 및 M2를 여러 번 분할한 후 x/2 + x%2 시퀀스를 얻습니다. , 그런 다음 병합 작업을 하나씩 수행합니다.

이 알고리즘의 특정 단계:

1. 첫 번째 포인터 왼쪽과 중간을 지정합니다(왼쪽은 시퀀스 1의 첫 번째 요소를 가리키고 오른쪽은 시퀀스 2의 첫 번째 요소를 가리킵니다)

2. 비교 왼쪽과 중간의 크기, 작은 요소를 새 공간에 넣습니다

　3. 시퀀스 중 하나가 탐색될 때까지 2단계를 반복합니다

　4. 추가되지 않은 나머지 요소를 새 공간에 직접 복사하여 붙여넣습니다. 새로운 공간으로

이 알고리즘 핵심 단계:

1. 분할 정복 방법(재귀)을 사용하여 시퀀스를 분할합니다.

2. 왼쪽과 중간의 크기를 비교하고 작은 추가

설명 뒤에 코드를 붙여넣습니다:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace 排序__归并排序
{
    class 归并
    {

        public static int[] arr = { 6, 202, 301, 100, 38, 8, 1 ,-1,1000};
        static void Main(string[] args)
        {
            Sort(arr, 0, arr.Length -1);
            foreach (var item in arr)
            {
                Console.Write(item + "  ");
            }
            Console.ReadKey();
        }

        public static void Sort(int []a,int left,int right)
        {
            if (left >= right) return;
            else
            {
                int mid = (left + right) / 2;                //@1
                Sort(a, left, mid);
                Sort(a, mid + 1, right);
                MergeSort(a, left, mid, right);
            }
        }

        public static void MergeSort(int []a,int left,int mid,int right)
        {
            int[] Arr = new int[right - left + 1];
            int l = left, m = mid +1 , k = 0;           //@2
            while ( m <= right && l <= mid )          //@3
            {
                if (a[l] > a[m]) Arr[k++] = a[m++];
                else Arr[k++] = a[l++];
            }
            while (m < right +1)                           //@4
            {
                Arr[k++] = a[m++];
            }
            while (l < mid +1 )  Arr[k++] = a[l++];        //@4
            for (k = 0, l = left; l < right + 1; k++, l++) a[l] = Arr[k];
        }
    }
}

코드 해석:

@1: Sort() 함수는 요소의 분할을 완료합니다. 각 재귀는 시퀀스를 분리할 수 없을 때까지 두 부분으로 나눕니다.

　 @2: l은 시퀀스 1의 첫 번째 요소를 나타내고, m은 시퀀스 2의 첫 번째 요소를 나타내며, k는 새 배열의 기존 요소 수를 나타냅니다. Arr

　 @3: 시퀀스 1의 첫 번째 요소를 첫 번째 요소와 비교합니다. 시퀀스 2의 요소, 작은 요소를 Arr에 넣고 시퀀스 중 하나의 요소가 비교될 때까지 시퀀스 커서를 뒤로 이동합니다. @4: 시퀀스 1과 시퀀스 2 간의 비교 프로세스 중에 시퀀스 1에 다음이 있는 것처럼 보일 수 있습니다. 모두 Arr 에 추가되었지만 시퀀스 2가 아직 없으면 비교되지 않은 나머지 요소를 Arr

요약: 에 직접 복사하세요.

　위의 코드는 실제 의미에서 배열을 분할하지 않습니다. 단지 논리적 분할을 수행하는 것뿐입니다. 다른 코드처럼 분할된 배열을 새 배열로 채우지는 않지만 속도와 메모리에는 약간의 영향이 있습니다. 이지만 결국 그렇게 좋지는 않습니다. 병합 작업에서 매개변수가 경계를 넘지 않도록 주의해야 합니다. (@2 위의 m이 왜 mid +1과 같아야 하는지 오랫동안 생각했습니다. 사실 이유는 매우 간단합니다. mid는 왼쪽 시퀀스에 속하고, mid+1부터 오른쪽 시퀀스에만 속하기 때문입니다. m = mid +1을 m =으로 변경하는 것은 불가능하지 않습니다. mid인데 후속 코드도 바꿔야 하는데 쓸데없는 비교를 하나 더 할 필요가 없군요. 당시에는 이 문제에 대해 정말 오랫동안 고민하고 있었습니다....) 사실, 논리적 관계가 명확하면 코드를 쉽게 파악할 수 있습니다.

위 내용은 정렬 알고리즘 - 병합 정렬 [코드 포함]의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!