Python 정렬 알고리즘의 병합 정렬을 구현하는 방법

알고리즘 설명

이 섹션의 첫 번째 고급 정렬 알고리즘은 병합 정렬입니다. 합병(merger)이라는 말은 '합병하다'라는 뜻이다. 이름에서 알 수 있듯이 병합 정렬 알고리즘은 먼저 시퀀스를 하위 시퀀스로 분할하고, 하위 시퀀스를 정렬한 다음, 정렬된 하위 시퀀스를 완전한 정렬된 시퀀스로 병합하는 알고리즘입니다. 실제로 분할 정복이라는 아이디어를 채택했습니다.

병합 정렬의 평균 시간 복잡도는 O(nlgn)이고, 최상의 경우의 시간 복잡도는 O(nlgn)이며, 최악의 경우의 시간 복잡도도 O(nlgn)입니다. 공간 복잡도는 O(1)입니다. 또한 병합 정렬은 안정적인 정렬 알고리즘입니다.

오름차순 정렬을 예로 들어 병합 알고리즘의 프로세스는 그림 2-21에 나와 있습니다.

원래 배열은 8개 숫자의 순서가 없는 배열입니다. 한 번의 작업 후에 8개 숫자의 배열은 순서가 지정되지 않은 4개 숫자 배열 2개로 나뉩니다. 각 작업은 모든 가장 작은 하위 배열에 하나의 요소만 포함될 때까지 순서가 지정되지 않은 배열을 절반으로 분할합니다. 배열에 요소가 하나만 있는 경우 배열을 정렬해야 합니다. 그런 다음 프로그램은 두 개의 작은 정렬된 배열을 큰 정렬된 배열로 병합하기 시작합니다. 먼저, 하나의 숫자를 포함하는 두 개의 배열을 두 개의 숫자를 포함하는 배열로 병합한 다음, 두 개의 숫자를 포함하는 두 개의 배열을 네 개의 숫자를 포함하는 배열로 병합하고, 마지막으로 두 개의 숫자를 포함하는 두 개의 배열을 여덟 개의 숫자를 포함하는 배열로 병합합니다. 모든 정렬된 배열이 결합되면 형성된 가장 긴 정렬된 배열이 정렬됩니다.

코드 구현

병합 정렬 코드:

  #归并排序
nums = [5,3,6,4,1,2,8,7]
def MergeSort(num):
  if(len(num)<=1):　　　　　　　　#递归边界条件
   return num　　　　　　　　　#到达边界时返回当前的子数组
  mid = int(len(num)/2)　　　　　 #求出数组的中位数
  llist,rlist = MergeSort(num[:mid]),MergeSort(num[mid:])#调用函数分别为左右数组排序
  result = []
  i,j = 0,0
  while i < len(llist) and j < len(rlist): #while循环用于合并两个有序数组
   if rlist[j]<llist[i]:
     result.append(rlist[j])
     j += 1
   else:
     result.append(llist[i])
     i += 1
  result += llist[i:]+rlist[j:]　 #把数组未添加的部分加到结果数组末尾
  return result　　　　　　　　　#返回已排序的数组
print(MergeSort(nums))

프로그램을 실행하면 출력 결과는 다음과 같습니다.

[1,2,3,4,5,6,7,8]

MergeSort() 함수에서 가장 먼저 해야 할 일은 경계 조건을 판단하는 것입니다. 요소가 하나만 포함된 배열이 함수 매개 변수로 전달되면 해당 요소만 배열에 존재하므로 배열이 최소 크기에 도달한 것입니다. 배열을 재귀적으로 분해하는 작업을 마친 후에는 분해된 배열을 이전 재귀 수준으로 되돌리면 됩니다.

정렬되지 않은 배열의 길이가 여전히 1보다 큰 경우 mid 변수를 사용하여 배열의 중간 첨자를 저장하고 정렬되지 않은 배열을 왼쪽과 오른쪽의 두 하위 배열로 나눕니다. 그런 다음 두 개의 새 배열을 만들어 정렬된 왼쪽 및 오른쪽 하위 배열을 저장합니다. 여기서는 재귀라는 개념이 사용됩니다. 우리는 MergeSort() 함수를 목록을 정렬하는 함수로만 생각합니다. 비록 MergeSort() 함수 내에서 함수 자체를 호출하여 두 개의 하위 배열을 정렬할 수도 있습니다.

그런 다음 while 루프를 사용하여 이미 정렬된 두 배열을 병합합니다. 두 배열에 있는 요소의 상대적 크기를 결정할 수 없기 때문에 두 개의 변수 i와 j를 사용하여 각각 왼쪽 하위 배열과 오른쪽 하위 배열에 추가되기를 기다리는 요소의 위치를 ​​표시합니다. while 루프가 끝나면 결과 목록에 추가되지 않은 하위 배열 끝에 가장 큰 요소가 남아 있을 수 있으므로 result+=llist[i:]+rlist[j:] 문은 이러한 요소를 방지하는 것입니다. 놓치는 것으로부터. 배열 병합이 완료된 후 함수는 정렬된 배열을 출력합니다.

위 내용은 Python 정렬 알고리즘의 병합 정렬을 구현하는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!