백엔드 개발 파이썬 튜토리얼 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 尊渡假赌尊渡假赌尊渡假赌
WWE 2K25 : Myrise에서 모든 것을 잠금 해제하는 방법
3 몇 주 전 By 尊渡假赌尊渡假赌尊渡假赌

뜨거운 도구

메모장++7.3.1

메모장++7.3.1

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

SublimeText3 중국어 버전

SublimeText3 중국어 버전

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

스튜디오 13.0.1 보내기

스튜디오 13.0.1 보내기

강력한 PHP 통합 개발 환경

드림위버 CS6

드림위버 CS6

시각적 웹 개발 도구

SublimeText3 Mac 버전

SublimeText3 Mac 버전

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

PS가 계속 로딩을 보여주는 이유는 무엇입니까? PS가 계속 로딩을 보여주는 이유는 무엇입니까? Apr 06, 2025 pm 06:39 PM

PS "로드"문제는 자원 액세스 또는 처리 문제로 인한 것입니다. 하드 디스크 판독 속도는 느리거나 나쁘다 : CrystalDiskinfo를 사용하여 하드 디스크 건강을 확인하고 문제가있는 하드 디스크를 교체하십시오. 불충분 한 메모리 : 고해상도 이미지 및 복잡한 레이어 처리에 대한 PS의 요구를 충족시키기 위해 메모리 업그레이드 메모리. 그래픽 카드 드라이버는 구식 또는 손상됩니다. 운전자를 업데이트하여 PS와 그래픽 카드 간의 통신을 최적화하십시오. 파일 경로는 너무 길거나 파일 이름에는 특수 문자가 있습니다. 짧은 경로를 사용하고 특수 문자를 피하십시오. PS 자체 문제 : PS 설치 프로그램을 다시 설치하거나 수리하십시오.

PS가 시작될 때 로딩 문제를 해결하는 방법은 무엇입니까? PS가 시작될 때 로딩 문제를 해결하는 방법은 무엇입니까? Apr 06, 2025 pm 06:36 PM

부팅 할 때 "로드"에 PS가 붙어있는 여러 가지 이유로 인해 발생할 수 있습니다. 손상되거나 충돌하는 플러그인을 비활성화합니다. 손상된 구성 파일을 삭제하거나 바꾸십시오. 불충분 한 메모리를 피하기 위해 불필요한 프로그램을 닫거나 메모리를 업그레이드하십시오. 하드 드라이브 독서 속도를 높이기 위해 솔리드 스테이트 드라이브로 업그레이드하십시오. 손상된 시스템 파일 또는 설치 패키지 문제를 복구하기 위해 PS를 다시 설치합니다. 시작 오류 로그 분석의 시작 과정에서 오류 정보를 봅니다.

PS가 파일을 열 때로드 문제를 해결하는 방법은 무엇입니까? PS가 파일을 열 때로드 문제를 해결하는 방법은 무엇입니까? Apr 06, 2025 pm 06:33 PM

"로드"는 PS에서 파일을 열 때 말더듬이 발생합니다. 그 이유에는 너무 크거나 손상된 파일, 메모리 불충분, 하드 디스크 속도가 느리게, 그래픽 카드 드라이버 문제, PS 버전 또는 플러그인 충돌이 포함될 수 있습니다. 솔루션은 다음과 같습니다. 파일 크기 및 무결성 확인, 메모리 증가, 하드 디스크 업그레이드, 그래픽 카드 드라이버 업데이트, 의심스러운 플러그인 제거 또는 비활성화 및 PS를 다시 설치하십시오. 이 문제는 PS 성능 설정을 점차적으로 확인하고 잘 활용하고 우수한 파일 관리 습관을 개발함으로써 효과적으로 해결할 수 있습니다.

설치 후 MySQL을 사용하는 방법 설치 후 MySQL을 사용하는 방법 Apr 08, 2025 am 11:48 AM

이 기사는 MySQL 데이터베이스의 작동을 소개합니다. 먼저 MySQLworkBench 또는 명령 줄 클라이언트와 같은 MySQL 클라이언트를 설치해야합니다. 1. MySQL-Uroot-P 명령을 사용하여 서버에 연결하고 루트 계정 암호로 로그인하십시오. 2. CreateABase를 사용하여 데이터베이스를 작성하고 데이터베이스를 선택하십시오. 3. CreateTable을 사용하여 테이블을 만들고 필드 및 데이터 유형을 정의하십시오. 4. InsertInto를 사용하여 데이터를 삽입하고 데이터를 쿼리하고 업데이트를 통해 데이터를 업데이트하고 DELETE를 통해 데이터를 삭제하십시오. 이러한 단계를 마스터하고 일반적인 문제를 처리하는 법을 배우고 데이터베이스 성능을 최적화하면 MySQL을 효율적으로 사용할 수 있습니다.

PS 페더 링은 어떻게 전환의 부드러움을 제어합니까? PS 페더 링은 어떻게 전환의 부드러움을 제어합니까? Apr 06, 2025 pm 07:33 PM

깃털 통제의 열쇠는 점진적인 성격을 이해하는 것입니다. PS 자체는 그라디언트 곡선을 직접 제어하는 ​​옵션을 제공하지 않지만 여러 깃털, 일치하는 마스크 및 미세 선택으로 반경 및 구배 소프트를 유연하게 조정하여 자연스럽게 전이 효과를 달성 할 수 있습니다.

MySQL은 지불해야합니다 MySQL은 지불해야합니다 Apr 08, 2025 pm 05:36 PM

MySQL에는 무료 커뮤니티 버전과 유료 엔터프라이즈 버전이 있습니다. 커뮤니티 버전은 무료로 사용 및 수정할 수 있지만 지원은 제한되어 있으며 안정성이 낮은 응용 프로그램에 적합하며 기술 기능이 강합니다. Enterprise Edition은 안정적이고 신뢰할 수있는 고성능 데이터베이스가 필요하고 지원 비용을 기꺼이 지불하는 응용 프로그램에 대한 포괄적 인 상업적 지원을 제공합니다. 버전을 선택할 때 고려 된 요소에는 응용 프로그램 중요도, 예산 책정 및 기술 기술이 포함됩니다. 완벽한 옵션은없고 가장 적합한 옵션 만 있으므로 특정 상황에 따라 신중하게 선택해야합니다.

MySQL 설치 후 데이터베이스 성능을 최적화하는 방법 MySQL 설치 후 데이터베이스 성능을 최적화하는 방법 Apr 08, 2025 am 11:36 AM

MySQL 성능 최적화는 설치 구성, 인덱싱 및 쿼리 최적화, 모니터링 및 튜닝의 세 가지 측면에서 시작해야합니다. 1. 설치 후 innodb_buffer_pool_size 매개 변수와 같은 서버 구성에 따라 my.cnf 파일을 조정해야합니다. 2. 과도한 인덱스를 피하기 위해 적절한 색인을 작성하고 Execution 명령을 사용하여 실행 계획을 분석하는 것과 같은 쿼리 문을 최적화합니다. 3. MySQL의 자체 모니터링 도구 (showprocesslist, showstatus)를 사용하여 데이터베이스 건강을 모니터링하고 정기적으로 백업 및 데이터베이스를 구성하십시오. 이러한 단계를 지속적으로 최적화함으로써 MySQL 데이터베이스의 성능을 향상시킬 수 있습니다.

PS 카드가 로딩 인터페이스에 있으면 어떻게해야합니까? PS 카드가 로딩 인터페이스에 있으면 어떻게해야합니까? Apr 06, 2025 pm 06:54 PM

PS 카드의로드 인터페이스는 소프트웨어 자체 (파일 손상 또는 플러그인 충돌), 시스템 환경 (DIFE 드라이버 또는 시스템 파일 손상) 또는 하드웨어 (하드 디스크 손상 또는 메모리 스틱 고장)로 인해 발생할 수 있습니다. 먼저 컴퓨터 자원이 충분한 지 확인하고 배경 프로그램을 닫고 메모리 및 CPU 리소스를 릴리스하십시오. PS 설치를 수정하거나 플러그인의 호환성 문제를 확인하십시오. PS 버전을 업데이트하거나 폴백합니다. 그래픽 카드 드라이버를 확인하고 업데이트하고 시스템 파일 확인을 실행하십시오. 위의 문제를 해결하면 하드 디스크 감지 및 메모리 테스트를 시도 할 수 있습니다.

See all articles