찾다
C# 병합 정렬Feb 09, 2017 pm 04:17 PM

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) 방식을 사용하는 매우 일반적인 응용 프로그램입니다.

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

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

C# 병합 정렬


위 그림에서 알 수 있듯이 먼저 정렬되지 않은 시퀀스를 가운데부터 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)를 참고해주세요!


성명
본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.
C 언어로 Null의 대안은 무엇입니까?C 언어로 Null의 대안은 무엇입니까?Mar 03, 2025 pm 05:37 PM

이 기사는 C의 Null 포인터 단축의 도전에 대해 탐구합니다. 그것은 문제가 그 자체가 아니라 오용한다고 주장합니다. 이 기사는 사전 수준 점검, 포인터 이니셜을 포함한 수반을 방지하기위한 모범 사례에 대해 자세히 설명합니다.

차세대 C 컴파일러를 추가하는 방법차세대 C 컴파일러를 추가하는 방법Mar 03, 2025 pm 05:44 PM

이 기사에서는 printf 내에서 \ n 탈출 시퀀스를 사용하여 C에서 Newline 문자를 만드는 방법을 설명하고 함수를 넣습니다. 기능을 자세히 설명하고 출력에서 ​​라인 브레이크 사용을 보여주는 코드 예제를 제공합니다.

어떤 C 언어 컴파일러가 더 낫습니까?어떤 C 언어 컴파일러가 더 낫습니까?Mar 03, 2025 pm 05:39 PM

이 기사는 초보자가 C 컴파일러를 선택하도록 안내합니다. GCC는 사용 편의성, 광범위한 가용성 및 광범위한 리소스로 인해 초보자에게 가장 적합하다고 주장합니다. 그러나 GCC, Clang, MSVC 및 TCC도 비교하여 차이를 강조합니다.

Null은 C 언어로 된 현대 프로그래밍에서 여전히 중요합니까?Null은 C 언어로 된 현대 프로그래밍에서 여전히 중요합니까?Mar 03, 2025 pm 05:35 PM

이 기사는 현대 C 프로그래밍에서 NULL의 지속적인 중요성을 강조합니다. 발전에도 불구하고 NULL은 명시적인 포인터 관리에 중요하며, 유효한 메모리 주소가 없음을 표시하여 세분화 결함을 방지합니다. 최고의 PRAC

C 언어 컴파일러의 웹 버전은 무엇입니까?C 언어 컴파일러의 웹 버전은 무엇입니까?Mar 03, 2025 pm 05:42 PM

이 기사에서는 초보자를위한 온라인 C 컴파일러를 검토하여 사용 편의성 및 디버깅 기능에 중점을 둡니다. OnlineGDB 및 Repl.it는 사용자 친화적 인 인터페이스 및 유용한 디버깅 도구를 위해 강조 표시됩니다. 프로그램 및 컴파일과 같은 다른 옵션

C 언어 온라인 프로그래밍 웹 사이트 C 언어 컴파일러 공식 웹 사이트 요약C 언어 온라인 프로그래밍 웹 사이트 C 언어 컴파일러 공식 웹 사이트 요약Mar 03, 2025 pm 05:41 PM

이 기사는 온라인 C 프로그래밍 플랫폼을 비교하여 디버깅 도구, IDE 기능, 표준 컴플라이언스 및 메모리/실행 제한과 같은 기능의 차이점을 강조합니다. "최고의"플랫폼은 사용자의 요구에 달려 있다고 주장합니다.

C 언어 컴파일러에 의해 코드를 복사하는 방법C 언어 컴파일러에 의해 코드를 복사하는 방법Mar 03, 2025 pm 05:43 PM

이 기사에서는 C IDE의 효율적인 코드 복사에 대해 설명합니다. 복사는 컴파일러 기능이 아닌 IDE 기능이며 IDE 선택 도구 사용, 코드 폴딩, 검색/교체, Templa를 포함하여 효율성 향상을위한 세부 사항 전략을 강조합니다.

C 언어 컴파일러에 의해 출력 창을 팝업하지 않는 문제를 해결하는 방법C 언어 컴파일러에 의해 출력 창을 팝업하지 않는 문제를 해결하는 방법Mar 03, 2025 pm 05:40 PM

이 기사는 C 프로그램 컴파일에서 누락 된 출력 창을 문제 해결합니다. 실행 가능, 프로그램 오류, 잘못된 컴파일러 설정, 백그라운드 프로세스 및 빠른 프로그램 종료와 같은 원인을 검사합니다. 솔루션은 ch

See all articles

핫 AI 도구

Undresser.AI Undress

Undresser.AI Undress

사실적인 누드 사진을 만들기 위한 AI 기반 앱

AI Clothes Remover

AI Clothes Remover

사진에서 옷을 제거하는 온라인 AI 도구입니다.

Undress AI Tool

Undress AI Tool

무료로 이미지를 벗다

Clothoff.io

Clothoff.io

AI 옷 제거제

AI Hentai Generator

AI Hentai Generator

AI Hentai를 무료로 생성하십시오.

뜨거운 도구

안전한 시험 브라우저

안전한 시험 브라우저

안전한 시험 브라우저는 온라인 시험을 안전하게 치르기 위한 보안 브라우저 환경입니다. 이 소프트웨어는 모든 컴퓨터를 안전한 워크스테이션으로 바꿔줍니다. 이는 모든 유틸리티에 대한 액세스를 제어하고 학생들이 승인되지 않은 리소스를 사용하는 것을 방지합니다.

SublimeText3 Linux 새 버전

SublimeText3 Linux 새 버전

SublimeText3 Linux 최신 버전

SublimeText3 중국어 버전

SublimeText3 중국어 버전

중국어 버전, 사용하기 매우 쉽습니다.

메모장++7.3.1

메모장++7.3.1

사용하기 쉬운 무료 코드 편집기

SublimeText3 Mac 버전

SublimeText3 Mac 버전

신 수준의 코드 편집 소프트웨어(SublimeText3)