python 기본 알고리즘 병합 정렬(Merge sort)
알고리즘 의 좋 고 나 쁨 을 평가 하 는 기준:
시간 복잡 도
공간 복잡 도
1.병합 정렬 알고리즘 은 무엇 입 니까?
거품 정렬(Bubble Sort)은 병합 작업 위 에 세 워 진 효과 적 인 정렬 알고리즘 으로 John von neumann 이 1945 년 에 발명 했다.분 치 법(Divide and Conquer)의 전형 적 인 응용 을 사용 합 니 다!!규모 가 큰 정렬 문 제 를 작은 규모 로 해결 하 다.
기본적으로 다음 과 같은 두 가지 방법 을 포함한다.
위 에서 아래로 의 귀환
아래 에서 위로 의 교체
이미 있 는 질서 있 는 하위 서열 을 합 쳐 완전히 질서 있 는 하위 서열 을 얻 을 수 있 습 니 다.먼저 모든 하위 서열 의 질 서 를 얻 은 다음 에 두 개의 하위 서열 을 하나 로 통합 시 키 는 것 이다.만약 두 개의 질서 표를 하나 로 합치 면,두 개의 질서 표 가 되 고,두 개의 질서 표 가 된다.
병합 정렬 의 성능 은 입력 데이터 의 영향 을 받 지 않 습 니 다.이것 은 선택 정렬 과 같 지만 성능 은 선택 정렬 보다 좋 고 성능 은 항상 O(n log n)입 니 다.그러나 성능 의 우수 성 은 반드시 추가 메모리 공간 이 큰 대가 가 될 것 이다!
2.알고리즘 프로 세 스 도해
3.코드 구현
코드 는 다음 과 같 습 니 다(예시 01):
"""
Merge_Sort
Divide and Conquer
：
"""
#
def merge_sort(alist):
# 1 ，
if len(alist) <= 1:
return alist
#
mid_index = len(alist)//2
#
# left_list = alist[:mid_index]
# right_list = alist[mid_index:]
# ，
left_list = merge_sort(alist[:mid_index])
right_list = merge_sort(alist[mid_index:])
return merge(left_list, right_list)
#
def merge(left_list, right_list):
l_index,r_index = 0,0
merge_list = []
#
while l_index < len(left_list) and r_index < len(right_list):
# ，
if left_list[l_index] < right_list[r_index]:
merge_list.append(left_list[l_index])
l_index += 1
else:
merge_list.append(right_list[r_index])
r_index += 1
# ， ， merge_list
merge_list += left_list[l_index:]
merge_list += right_list[r_index:]
return merge_list
if __name__ == '__main__':
alist = [54, 26, 93, 17, 77, 31, 44, 55, 20]
print(f' ：{alist}')
alist = merge_sort(alist)
print(f' ：{alist}')
4.평판 알고리즘
가장 좋 은 시간 복잡 도:O(n log n)최 악의 시간 복잡 도:O(n log n)평균 시간 복잡 도:O(n log n)공간 복잡 도:O(n)알고리즘 안정성:안정 적 인 정렬총결산
python 기본 알고리즘 의 병합 정렬(Merge sort)에 관 한 이 글 은 여기까지 소개 되 었 습 니 다.더 많은 관련 python 병합 정렬(Merge sort)내용 은 우리 의 이전 글 을 검색 하거나 아래 의 관련 글 을 계속 찾 아 보 세 요.앞으로 도 많은 응원 부 탁 드 리 겠 습 니 다!
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
로마 숫자를 정수로 또는 그 반대로 변환그 중 하나는 로마 숫자를 정수로 변환하는 함수를 만드는 것이었고 두 번째는 그 반대를 수행하는 함수를 만드는 것이었습니다. 문자만 포함합니다'I', 'V', 'X', 'L', 'C', 'D', 'M' ; 문자열이 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
