파이썬 프로그래밍을 이용한 병합 정렬 방법 소개

이 글에서는 병합 정렬을 구현하기 위한 파이썬프로그래밍의 구체적인 코드를 주로 소개합니다. 관심 있는 친구들은 참고할 수 있습니다

. 지난 주 leetcode에 대한 질문(Median of Two Sorted Arrays)에서 병합 정렬의 구현을 자세히 살펴보고 싶었습니다.

먼저 정렬 아이디어를 설명하겠습니다.

먼저 병합 정렬은 이분법 방식을 사용합니다. 최종적으로는 분할하여 정복하는 아이디어입니다. 긴 배열을 가져와서 왼쪽과 오른쪽 부분으로 연속적으로 나눈 다음 재귀적으로 나눕니다. 그런 다음 이를 두 개의 정렬된 배열로 병합합니다. 이 방법으로는 이해하기 어려우실 수 있으니 제가 그린 그림을 보여드리겠습니다.

이것은 병합 정렬의 첫 번째 단계를 보여줍니다. middle에 따라 배열을 재귀적으로 분할하고 마지막으로 가장 작은 세부 사항으로 분할합니다. 정렬과 동일한 방법을 사용하여 두 개의 정렬된 배열을 정렬합니다.

두 개의 배열을 정렬하는 방법은 매우 간단합니다. 두 배열의 첫 번째 위치를 동시에 비교하여 더 작은 배열을 빈 배열에 넣은 다음, 빈 배열 위치의 포인터가 1만큼 뒤로 이동한 다음 계속해서 다른 배열의 이전 위치와 비교됩니다. 마지막 배열이 스택에서 먼저 팝되면 다른 배열의 모든 요소가 새 배열에 추가됩니다.

그러나 재귀 분할의 시간 복잡도는 logN이므로 두 개의 정렬된 배열을 정렬하는 방법의 복잡도는 N입니다. 이 알고리즘의 시간 복잡도는 N*logN이므로 NlogN입니다.

이번 분석에 따르면 위 사진의 행동을 살펴볼 수 있습니다.

가장 왼쪽 부분이 세세하게 나누어지면 더 이상 왼쪽과 오른쪽 부분으로 나눌 수 없게 되면서 합쳐지기 시작합니다.

첫 번째 조합으로 [4, 7] 병합 완료

두 번째 조합으로 [4, 7, 8] 병합 완료

세 번째 조합으로 [ 3, 5의 병합]

네 번째 조합이 완료되었습니다. [3, 5, 9]의 병합이 완료되었습니다.

다섯 번째 조합이 완료되었습니다. [3, 4, 5, 7, 8, 9 ] 병합하면 정렬이 종료됩니다.

아래에 파이썬 코드를 넣어보세요

def merge(a, b):
 c = []
 h = j = 0
 while j < len(a) and h < len(b):
  if a[j] < b[h]:
   c.append(a[j])
   j += 1
  else:
   c.append(b[h])
   h += 1

 if j == len(a):
  for i in b[h:]:
   c.append(i)
 else:
  for i in a[j:]:
   c.append(i)

 return c


def merge_sort(lists):
 if len(lists) <= 1:
  return lists
 middle = len(lists)/2
 left = merge_sort(lists[:middle])
 right = merge_sort(lists[middle:])
 return merge(left, right)


if name == &#39;main&#39;:
 a = [4, 7, 8, 3, 5, 9]
 print merge_sort(a)

위 내용은 파이썬 프로그래밍을 이용한 병합 정렬 방법 소개의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!