Python의 빠른 정렬 방법

이 글은 Python으로 구현된 퀵 정렬 알고리즘을 주로 소개하고, Python 퀵 정렬의 원리, 구현 방법, 관련 운영 기법을 예제 형식으로 분석해 놓은 것입니다. Python으로 구현된 빠른 정렬 알고리즘. 참고하실 수 있도록 자세한 내용은 다음과 같습니다.

빠른 정렬의 기본 아이디어는 정렬할 데이터를 한 번의 정렬 과정을 통해 두 개의 독립적인 부분으로 나누는 것입니다. 그런 다음 이 방법을 사용하면 데이터의 두 부분을 각각 빠르게 정렬할 수 있으므로 전체 정렬 프로세스를 반복적으로 수행할 수 있으므로 전체 데이터가 정렬된 시퀀스가 ​​됩니다.

예를 들어 [6, 8, 1, 4, 3, 9] 순서에서 염기 번호로 6을 선택하세요. 오른쪽에서 왼쪽으로 스캔하여 기본 숫자 3보다 작은 숫자를 찾고, 6과 3의 위치를 ​​바꾼 다음 [3, 8, 1, 4, 6, 9]를 왼쪽에서 오른쪽으로 스캔하여 숫자를 찾습니다. 기본 숫자보다 큰 숫자는 8입니다. 6과 8의 위치를 ​​바꿉니다. [3, 6, 1, 4, 8, 9]. 밑수 왼쪽의 숫자가 그것보다 작아지고 오른쪽의 숫자가 그것보다 커질 때까지 위의 과정을 반복합니다. 그런 다음 참조 번호의 왼쪽과 오른쪽에 있는 시퀀스에 대해 각각 위의 방법을 재귀적으로 수행합니다.

구현 코드는 다음과 같습니다.

def parttion(v, left, right):
  key = v[left]
  low = left
  high = right
  while low < high:
    while (low < high) and (v[high] >= key):
      high -= 1
    v[low] = v[high]
    while (low < high) and (v[low] <= key):
      low += 1
    v[high] = v[low]
    v[low] = key
  return low
def quicksort(v, left, right):
  if left < right:
    p = parttion(v, left, right)
    quicksort(v, left, p-1)
    quicksort(v, p+1, right)
  return v
s = [6, 8, 1, 4, 3, 9, 5, 4, 11, 2, 2, 15, 6]
print("before sort:",s)
s1 = quicksort(s, left = 0, right = len(s) - 1)
print("after sort:",s1)

실행 결과:

before sort: [6, 8, 1, 4, 3, 9, 5, 4, 11, 2, 2, 15, 6]
after sort: [1, 2, 2, 3, 4, 4, 5, 6, 6, 8, 9, 11, 15]

위 내용은 Python의 빠른 정렬 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!