백엔드 개발 파이썬 튜토리얼 Python을 사용하여 병합 정렬을 구현하는 방법

Python을 사용하여 병합 정렬을 구현하는 방법

Jun 11, 2023 am 08:46 AM
python 병합 정렬 종류

병합 정렬은 고전적인 정렬 알고리즘의 핵심 아이디어는 정렬할 배열을 여러 하위 배열로 나누고, 이러한 하위 배열을 정렬한 다음, 마지막으로 정렬된 하위 배열을 순서 있는 배열로 병합하는 것입니다. 병합 정렬은 시간 복잡도가 O(nlogn)인 비교적 효율적인 정렬 알고리즘입니다.

이 글에서는 Python에서 병합 정렬을 구현하는 방법을 설명하겠습니다.

  1. 병합 정렬 구현 아이디어

병합 정렬 구현 아이디어는 분할 정복과 병합이라는 두 부분으로 구성됩니다. 구체적인 구현 단계는 다음과 같습니다.

1) 정렬할 배열을 연속적으로 2개로 나누고, 왼쪽과 오른쪽 부분을 재귀적으로 정렬합니다.

2) 정렬된 왼쪽 부분과 오른쪽 부분을 순서 있는 배열로 병합합니다.

  1. Python을 사용하여 분할 정복 구현

분할 정복은 병합 정렬의 핵심 아이디어로 분할 정복 부분을 먼저 구현해야 합니다.

코드는 다음과 같습니다.

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left_arr = merge_sort(arr[:mid])
    right_arr = merge_sort(arr[mid:])
    return merge(left_arr, right_arr)
로그인 후 복사

이 함수에서는 먼저 배열 길이가 1보다 작거나 같은지 확인한 다음 배열을 직접 반환합니다. 그렇지 않으면 배열을 두 개로 나누고 각각 왼쪽과 오른쪽 부분을 재귀적으로 정렬한 다음 마지막으로 정렬된 왼쪽 부분과 오른쪽 부분을 병합해야 합니다.

2.1 합병 구현

분할과 정복을 바탕으로 병합 부분을 구현해야 합니다.

코드는 다음과 같습니다:

def merge(left_arr, right_arr):
    i, j = 0, 0
    result = []
    while i < len(left_arr) and j < len(right_arr):
        if left_arr[i] < right_arr[j]:
            result.append(left_arr[i])
            i += 1
        else:
            result.append(right_arr[j])
            j += 1
    result += left_arr[i:]
    result += right_arr[j:]
    return result
로그인 후 복사

이 함수에서는 먼저 왼쪽과 오른쪽 부분에서 각각 비교할 요소를 가리키는 포인터 i와 j를 초기화합니다. 그런 다음 왼쪽과 오른쪽 요소를 지속적으로 비교하고 더 작은 요소를 결과 목록에 추가한 다음 포인터를 오른쪽으로 이동합니다. 마지막으로 남은 모든 요소를 ​​결과 목록에 추가하여 정렬된 배열로 끝납니다.

  1. 전체 코드

분할 정복 및 병합 부분을 결합한 전체 코드는 다음과 같습니다.

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left_arr = merge_sort(arr[:mid])
    right_arr = merge_sort(arr[mid:])
    return merge(left_arr, right_arr)

def merge(left_arr, right_arr):
    i, j = 0, 0
    result = []
    while i < len(left_arr) and j < len(right_arr):
        if left_arr[i] < right_arr[j]:
            result.append(left_arr[i])
            i += 1
        else:
            result.append(right_arr[j])
            j += 1
    result += left_arr[i:]
    result += right_arr[j:]
    return result
로그인 후 복사
  1. Testing

병합 정렬 코드가 올바른지 확인하려면 테스트를 수행해야 합니다. .

코드는 다음과 같습니다.

arr = [5, 3, 8, 6, 4, 7, 2, 1]
print(merge_sort(arr))
로그인 후 복사

출력 결과는 다음과 같습니다.

[1, 2, 3, 4, 5, 6, 7, 8]

테스트 결과에 따르면 병합 정렬 코드가 올바른 것으로 나타났습니다.

위 내용은 Python을 사용하여 병합 정렬을 구현하는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!

본 웹사이트의 성명
본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.

핫 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를 무료로 생성하십시오.

인기 기사

R.E.P.O. 에너지 결정과 그들이하는 일 (노란색 크리스탈)
3 몇 주 전 By 尊渡假赌尊渡假赌尊渡假赌
R.E.P.O. 최고의 그래픽 설정
3 몇 주 전 By 尊渡假赌尊渡假赌尊渡假赌
R.E.P.O. 아무도들을 수없는 경우 오디오를 수정하는 방법
3 몇 주 전 By 尊渡假赌尊渡假赌尊渡假赌

뜨거운 도구

메모장++7.3.1

메모장++7.3.1

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

SublimeText3 중국어 버전

SublimeText3 중국어 버전

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

스튜디오 13.0.1 보내기

스튜디오 13.0.1 보내기

강력한 PHP 통합 개발 환경

드림위버 CS6

드림위버 CS6

시각적 웹 개발 도구

SublimeText3 Mac 버전

SublimeText3 Mac 버전

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

C 언어 합계의 기능은 무엇입니까? C 언어 합계의 기능은 무엇입니까? Apr 03, 2025 pm 02:21 PM

C 언어에는 내장 합계 기능이 없으므로 직접 작성해야합니다. 합계는 배열 및 축적 요소를 가로 질러 달성 할 수 있습니다. 루프 버전 : 루프 및 배열 길이를 사용하여 계산됩니다. 포인터 버전 : 포인터를 사용하여 배열 요소를 가리키며 효율적인 합계는 자체 증가 포인터를 통해 달성됩니다. 동적으로 배열 버전을 할당 : 배열을 동적으로 할당하고 메모리를 직접 관리하여 메모리 누출을 방지하기 위해 할당 된 메모리가 해제되도록합니다.

누가 더 많은 파이썬이나 자바 스크립트를 지불합니까? 누가 더 많은 파이썬이나 자바 스크립트를 지불합니까? Apr 04, 2025 am 12:09 AM

기술 및 산업 요구에 따라 Python 및 JavaScript 개발자에 대한 절대 급여는 없습니다. 1. 파이썬은 데이터 과학 및 기계 학습에서 더 많은 비용을 지불 할 수 있습니다. 2. JavaScript는 프론트 엔드 및 풀 스택 개발에 큰 수요가 있으며 급여도 상당합니다. 3. 영향 요인에는 경험, 지리적 위치, 회사 규모 및 특정 기술이 포함됩니다.

별개의 구별이 관련되어 있습니까? 별개의 구별이 관련되어 있습니까? Apr 03, 2025 pm 10:30 PM

구별되고 구별되는 것은 구별과 관련이 있지만, 다르게 사용됩니다. 뚜렷한 (형용사)는 사물 자체의 독창성을 묘사하고 사물 사이의 차이를 강조하는 데 사용됩니다. 뚜렷한 (동사)는 구별 행동이나 능력을 나타내며 차별 과정을 설명하는 데 사용됩니다. 프로그래밍에서 구별은 종종 중복 제거 작업과 같은 컬렉션에서 요소의 독창성을 나타내는 데 사용됩니다. 홀수 및 짝수 숫자를 구별하는 것과 같은 알고리즘이나 함수의 설계에 별개가 반영됩니다. 최적화 할 때 별도의 작업은 적절한 알고리즘 및 데이터 구조를 선택해야하며, 고유 한 작업은 논리 효율성의 구별을 최적화하고 명확하고 읽을 수있는 코드 작성에주의를 기울여야합니다.

이해하는 방법! x는? 이해하는 방법! x는? Apr 03, 2025 pm 02:33 PM

! x 이해! x는 C 언어로 된 논리적 비 운영자입니다. 그것은 x의 값, 즉 실제 변경, 거짓, 잘못된 변경 사항을 부수합니다. 그러나 C의 진실과 거짓은 부울 유형보다는 숫자 값으로 표시되며, 0이 아닌 것은 참으로 간주되며 0만이 거짓으로 간주됩니다. 따라서! x는 음수를 양수와 동일하게 처리하며 사실로 간주됩니다.

C 언어에서 합계는 무엇을 의미합니까? C 언어에서 합계는 무엇을 의미합니까? Apr 03, 2025 pm 02:36 PM

합에 대한 C에는 내장 합계 기능이 없지만 다음과 같이 구현할 수 있습니다. 루프를 사용하여 요소를 하나씩 축적합니다. 포인터를 사용하여 요소를 하나씩 액세스하고 축적합니다. 큰 데이터 볼륨의 경우 병렬 계산을 고려하십시오.

H5 페이지 생산에는 지속적인 유지 보수가 필요합니까? H5 페이지 생산에는 지속적인 유지 보수가 필요합니까? Apr 05, 2025 pm 11:27 PM

코드 취약점, 브라우저 호환성, 성능 최적화, 보안 업데이트 및 사용자 경험 개선과 같은 요소로 인해 H5 페이지를 지속적으로 유지해야합니다. 효과적인 유지 관리 방법에는 완전한 테스트 시스템 설정, 버전 제어 도구 사용, 페이지 성능을 정기적으로 모니터링하고 사용자 피드백 수집 및 유지 관리 계획을 수립하는 것이 포함됩니다.

58.com 작업 페이지에서 실시간 응용 프로그램 및 뷰어 데이터를 얻는 방법은 무엇입니까? 58.com 작업 페이지에서 실시간 응용 프로그램 및 뷰어 데이터를 얻는 방법은 무엇입니까? Apr 05, 2025 am 08:06 AM

크롤링하는 동안 58.com 작업 페이지의 동적 데이터를 얻는 방법은 무엇입니까? Crawler 도구를 사용하여 58.com의 작업 페이지를 크롤링 할 때는이 문제가 발생할 수 있습니다.

사랑 코드 복사 및 붙여 넣기 복사하여 사랑 코드를 무료로 붙여 넣으십시오. 사랑 코드 복사 및 붙여 넣기 복사하여 사랑 코드를 무료로 붙여 넣으십시오. Apr 04, 2025 am 06:48 AM

코드 복사 및 붙여 넣기는 불가능하지는 않지만주의해서 처리해야합니다. 코드의 환경, 라이브러리, 버전 등과 같은 종속성은 현재 프로젝트와 일치하지 않으므로 오류 또는 예측할 수없는 결과를 초래할 수 있습니다. 파일 경로, 종속 라이브러리 및 Python 버전을 포함하여 컨텍스트가 일관되게 유지하십시오. 또한 특정 라이브러리의 코드를 복사 및 붙여 넣을 때 라이브러리 및 해당 종속성을 설치해야 할 수도 있습니다. 일반적인 오류에는 경로 오류, 버전 충돌 및 일관되지 않은 코드 스타일이 포함됩니다. 성능 최적화는 코드의 원래 목적 및 제약에 따라 재 설계 또는 리팩토링되어야합니다. 복사 코드를 이해하고 디버그하고 맹목적으로 복사하여 붙여 넣지 않는 것이 중요합니다.

See all articles