기본 아이디어: 병합 정렬은 순서가 지정되지 않은 목록을 둘로 나눈 다음 각 하위 시퀀스를 다시 둘로 나누고 더 이상 나눌 수 없을 때까지 계속되는 전형적인 분할 정복 아이디어입니다. 그러면 병합 과정이 시작되어 각 하위 시퀀스의 요소를 다른 하위 시퀀스와 비교하고 작은 요소들을 병합할 결과 시퀀스에 순차적으로 넣어 최종적으로 병합 정렬이 완료됩니다.
병합 작업 과정:
정렬된 두 시퀀스의 합이 되도록 공백을 적용합니다. 이 공백은 병합된 시퀀스를 저장하는 데 사용됩니다. 🎜>두 개의 포인터를 설정하고 초기 위치는 각각 정렬된 두 시퀀스의 시작 위치입니다.
두 개의 포인터가 가리키는 요소를 비교하고 상대적으로 작은 요소를 선택하여 병합 공간에 넣은 후 포인터를 이동하여 다음 위치
특정 포인터가 시퀀스의 끝에 도달할 때까지 3단계를 반복합니다.
다른 시퀀스의 나머지 요소를 모두 병합된 시퀀스의 끝에 직접 복사합니다.
위의 설명은 이론적인 설명입니다. 다음은 설명할 수 있는 실제 예입니다.
[6,2,3,1,7]먼저 다음이 될 때까지 배열을 재귀적으로 분해합니다.
[6],[2],[3],[1],[7]그런 다음 재귀적인 방식으로 병합 정렬을 시작합니다. 2개씩 병합하고 정렬하면 다음을 얻습니다.
[2,6],[1,3],[7]이전 단계에서는 이번 단계의 방법으로 실제로 Merge를 하였는데, 각 목록에 숫자가 있어서 전체 과정을 표시할 수는 없습니다. 프로세스는 아래에서 완전히 볼 수 있습니다. 초기:
a = [2,6] b = [1,3] c = []1단계, a, b에서 숫자를 순서대로 꺼내어 2, 1, 크기를 비교하고 넣습니다. 이를 c 로 변환하고 원래 목록에서 숫자를 삭제하면 결과는 다음과 같습니다.
a = [2,6] b = [3] c = [1]2단계, 계속해서 a와 b에서 순서대로 숫자를 제거합니다. , 또한 위 단계를 반복하세요. 이번에는 2,3입니다. 크기를 비교하여 c에 넣으면 결과는 다음과 같습니다.
a = [6] b = [3] c = [1,2]3단계, 이전 단계를 반복하면 결과는 다음과 같습니다.
a = [6] b = [] c = [1,2,3]마지막 단계는 c에 6을 추가하는 것입니다. 결과는 다음과 같습니다.
a = [] b = [] c = [1,2,3,6]위의 과정을 반복적으로 적용하면 [1,2,3,6]과 [7]의 병합이 이루어집니다
마지막으로 정렬 결과를 얻습니다.
[1,2,3,6,7]
이 문서에는 세 가지 Python 구현 방법이 나열되어 있습니다.
방법 1: 위에서 설명한 프로세스를 번역합니다. 조금 어설프지만#! /usr/bin/env python #coding:utf-8 def merge_sort(seq): if len(seq) ==1: return seq else: middle = len(seq)/2 left = merge_sort(seq[:middle]) right = merge_sort(seq[middle:]) i = 0 #left 计数 j = 0 #right 计数 k = 0 #总计数 while i < len(left) and j < len(right): if left[i] < right [j]: seq[k] = left[i] i +=1 k +=1 else: seq[k] = right[j] j +=1 k +=1 remain = left if i<j else right r = i if remain ==left else j while r<len(remain): seq[k] = remain[r] r +=1 k +=1 return seq방법 2: 값을 순서대로 취하는 측면에서 list.pop () 메소드를 사용하여 코드가 더욱 컴팩트하고 간결해졌습니다
#! /usr/bin/env python #coding:utf-8 def merge_sort(lst): #此方法来自维基百科 if len(lst) <= 1: return lst def merge(left, right): merged = [] while left and right: merged.append(left.pop(0) if left[0] <= right[0] else right.pop(0)) while left: merged.append(left.pop(0)) while right: merged.append(right.pop(0)) return merged middle = int(len(lst) / 2) left = merge_sort(lst[:middle]) right = merge_sort(lst[middle:]) return merge(left, right)방법 3: 병합 정렬 방법이 제공되는 것으로 나타났습니다. Python 모듈 heapq. 분해된 결과를 이 메서드로 가져오기만 하면 됩니다.
#! /usr/bin/env python #coding:utf-8 from heapq import merge def merge_sort(seq): if len(seq) <= 1: return m else: middle = len(seq)/2 left = merge_sort(seq[:middle]) right = merge_sort(seq[middle:]) return list(merge(left, right)) #heapq.merge() if __name__=="__main__": seq = [1,3,6,2,4] print merge_sort(seq)Python 프로그래밍에서 병합 정렬 알고리즘의 구현 단계에 대한 자세한 소개는 PHP 중국어 웹사이트의 관련 기사에 주목하세요!