Python 프로그래밍에서 병합 정렬 알고리즘의 구현 단계에 대한 자세한 소개

기본 아이디어: 병합 정렬은 순서가 지정되지 않은 목록을 둘로 나눈 다음 각 하위 시퀀스를 다시 둘로 나누고 더 이상 나눌 수 없을 때까지 계속되는 전형적인 분할 정복 아이디어입니다. 그러면 병합 과정이 시작되어 각 하위 시퀀스의 요소를 다른 하위 시퀀스와 비교하고 작은 요소들을 병합할 결과 시퀀스에 순차적으로 넣어 최종적으로 병합 정렬이 완료됩니다.

병합 작업 과정:

정렬된 두 시퀀스의 합이 되도록 공백을 적용합니다. 이 공백은 병합된 시퀀스를 저장하는 데 사용됩니다. 🎜>두 개의 포인터를 설정하고 초기 위치는 각각 정렬된 두 시퀀스의 시작 위치입니다.
두 개의 포인터가 가리키는 요소를 비교하고 상대적으로 작은 요소를 선택하여 병합 공간에 넣은 후 포인터를 이동하여 다음 위치
특정 포인터가 시퀀스의 끝에 도달할 때까지 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 중국어 웹사이트의 관련 기사에 주목하세요!