Python에서 8가지 정렬 알고리즘을 구현하는 방법

이 기사에서는 주로 8가지 정렬 알고리즘의 Python 구현을 소개하고, 8가지 정렬 알고리즘에 대한 자세한 설명과 코드 구현을 제공합니다. 관심 있는 친구는

8가지 정렬 알고리즘의 Python 구현을 참조하세요. 내용은 다음과 같습니다

1. 삽입 정렬
설명

삽입 정렬의 기본 동작은 정렬된 데이터에 데이터를 삽입하는 것입니다. 숫자에 1을 더한 새로운 순서의 데이터를 얻습니다. 이 알고리즘은 소량의 데이터를 정렬하는 데 적합하며 시간 복잡도는 O(n^2)입니다. 안정적인 정렬 방법입니다. 삽입 알고리즘은 정렬할 배열을 두 부분으로 나눕니다. 첫 번째 부분에는 마지막 요소를 제외한 배열의 모든 요소가 포함되며(배열에 삽입 위치를 확보할 수 있는 공간이 하나 더 추가됨) 두 번째 부분에는 이 요소만 포함됩니다. 하나의 요소(즉, 삽입할 요소). 첫 번째 부분이 정렬된 후 이 마지막 요소가 정렬된 첫 번째 부분에 삽입됩니다.

코드 구현

def insert_sort(lists):
  # 插入排序
  count = len(lists)
  for i in range(1, count):
    key = lists[i]
    j = i - 1
    while j >= 0:
      if lists[j] > key:
        lists[j + 1] = lists[j]
        lists[j] = key
      j -= 1
  return lists

2. Hill 정렬
설명

Hill 정렬( Shell Sort)는 삽입 정렬의 한 종류입니다. 증분 정렬 감소라고도 하며, 직접 삽입 정렬 알고리즘보다 효율적이고 향상된 버전입니다. Hill 정렬은 불안정한 정렬 알고리즘입니다. 이 방법은 DL 때문입니다. Shell은 1959년 제안된 이름을 따서 명명되었습니다. Hill 정렬은 첨자의 특정 증분으로 그룹을 기록하고 직접 삽입 정렬 알고리즘을 사용하여 각 그룹을 정렬합니다. 증분이 점차 감소함에 따라 각 그룹에는 점점 더 많은 키워드가 포함되며 전체 파일이 그룹화됩니다. 정확히 하나의 그룹으로 분류되고 알고리즘이 종료됩니다.

코드 구현

def shell_sort(lists):
  # 希尔排序
  count = len(lists)
  step = 2
  group = count / step
  while group > 0:
    for i in range(0, group):
      j = i + group
      while j < count:
        k = j - group
        key = lists[j]
        while k >= 0:
          if lists[k] > key:
            lists[k + group] = lists[k]
            lists[k] = key
          k -= group
        j += group
    group /= step
  return lists

3. 버블 정렬
설명

반복됩니다. 정렬할 순서를 살펴보고 한 번에 두 개의 요소를 비교하고 순서가 잘못된 경우 교체합니다. 더 이상 교환이 필요하지 않을 때까지 어레이 방문 작업이 반복됩니다. 이는 어레이가 정렬되었음을 의미합니다.

코드 구현

def bubble_sort(lists):
  # 冒泡排序
  count = len(lists)
  for i in range(0, count):
    for j in range(i + 1, count):
      if lists[i] > lists[j]:
        lists[i], lists[j] = lists[j], lists[i]
  return lists

4. Quick sort
설명

pass through Sorting 정렬할 데이터를 두 개의 독립적인 부분으로 나눕니다. 한 부분의 모든 데이터는 다른 부분의 모든 데이터보다 작습니다. 그런 다음 이 방법에 따라 데이터의 두 부분을 빠르게 정렬할 수 있습니다. 이러한 방식으로 전체 데이터는 순서가 지정된 시퀀스가 ​​됩니다.

코드 구현

def quick_sort(lists, left, right):
  # 快速排序
  if left >= right:
    return lists
  key = lists[left]
  low = left
  high = right
  while left < right:
    while left < right and lists[right] >= key:
      right -= 1
    lists[left] = lists[right]
    while left < right and lists[left] <= key:
      left += 1
    lists[right] = lists[left]
  lists[right] = key
  quick_sort(lists, low, left - 1)
  quick_sort(lists, left + 1, high)
  return lists

5. 직접 선택 정렬
설명

기본 아이디어 : 1차 패스에서는 정렬할 레코드 r1 ~ r[n] 중 가장 작은 레코드를 선택하고, 2차 패스에서는 정렬할 레코드 r2 ~ r[n] 중 가장 작은 레코드를 선택한다. , r1과 교환합니다. r2와 교환하는 식으로, i번째 패스에서는 r[i] ~ r[n]으로 정렬할 레코드 중 가장 작은 레코드를 선택하여 r[i]와 교환합니다. 정렬된 시퀀스는 모두 정렬이 완료될 때까지 계속 증가합니다.

코드 구현

def select_sort(lists):
  # 选择排序
  count = len(lists)
  for i in range(0, count):
    min = i
    for j in range(i + 1, count):
      if lists[min] > lists[j]:
        min = j
    lists[min], lists[i] = lists[i], lists[min]
  return lists

6. 힙 정렬
설명

힙 정렬( 힙 정렬(Heapsort)은 스택 트리(힙)와 같은 데이터 구조를 사용하여 설계된 정렬 알고리즘을 말합니다. 선택 정렬의 한 종류입니다. 배열의 특성을 사용하여 지정된 인덱스에서 요소를 빠르게 찾을 수 있습니다. 힙은 큰 루트 힙과 작은 루트 힙으로 나누어지며 이는 완전한 이진 트리입니다. 큰 루트 힙의 요구 사항은 각 노드의 값이 해당 상위 노드의 값, 즉 A[PARENT[i]] >= A[i]보다 크지 않아야 한다는 것입니다. 배열의 비내림차순 정렬에서는 큰 루트 힙의 요구 사항에 따라 가장 큰 값이 힙의 맨 위에 있어야 하기 때문에 큰 루트 힙을 사용해야 합니다.

코드 구현

# 调整堆
def adjust_heap(lists, i, size):
  lchild = 2 * i + 1
  rchild = 2 * i + 2
  max = i
  if i < size / 2:
    if lchild < size and lists[lchild] > lists[max]:
      max = lchild
    if rchild < size and lists[rchild] > lists[max]:
      max = rchild
    if max != i:
      lists[max], lists[i] = lists[i], lists[max]
      adjust_heap(lists, max, size)

# 创建堆
def build_heap(lists, size):
  for i in range(0, (size/2))[::-1]:
    adjust_heap(lists, i, size)

# 堆排序
def heap_sort(lists):
  size = len(lists)
  build_heap(lists, size)
  for i in range(0, size)[::-1]:
    lists[0], lists[i] = lists[i], lists[0]
    adjust_heap(lists, 0, i)

7. 병합 정렬
설명

병합 정렬은 병합 연산을 기반으로 한 효과적인 정렬 알고리즘은 분할 및 정복 방법(pide 및 Conquer)의 매우 일반적인 응용 프로그램입니다. 이미 정렬된 하위 시퀀스를 병합하여 완전히 정렬된 시퀀스를 얻습니다. 즉, 먼저 각 하위 시퀀스를 순서대로 만든 다음 하위 시퀀스 세그먼트를 순서대로 만듭니다. 두 개의 순서 목록이 하나의 순서 목록으로 병합되는 경우 이를 양방향 병합이라고 합니다.

병합 과정은 a[i]와 a[j]의 크기를 비교하고, a[i]≤a[j]인 경우 첫 번째 순서 목록의 a[i] 요소를 r에 복사합니다. [k], i와 k에 각각 1을 추가합니다. 그렇지 않으면 두 번째 순서 목록의 요소 a[j]를 r[k]에 복사하고 j와 k에 각각 1을 추가합니다. 이 주기는 순서가 지정된 목록 중 하나가 나올 때까지 계속됩니다. 목록을 가져온 다음 다른 순서 목록의 나머지 요소를 아래 첨자 k에서 아래 첨자 t까지 r의 셀에 복사합니다. 우리는 병합 정렬 알고리즘을 구현하기 위해 일반적으로 재귀를 사용합니다. 먼저 정렬할 간격 [s, t]를 중간점을 기준으로 2개로 나눈 다음 왼쪽 하위 범위를 정렬한 다음 오른쪽 하위 범위를 정렬합니다. 마지막으로 왼쪽 간격과 오른쪽 간격이 순서가 지정된 간격 [s,t]로 병합됩니다.

코드 구현

def merge(left, right):
  i, j = 0, 0
  result = []
  while i < len(left) and j < len(right):
    if left[i] <= right[j]:
      result.append(left[i])
      i += 1
    else:
      result.append(right[j])
      j += 1
  result += left[i:]
  result += right[j:]
  return result

def merge_sort(lists):
  # 归并排序
  if len(lists) <= 1:
    return lists
  num = len(lists) / 2
  left = merge_sort(lists[:num])
  right = merge_sort(lists[num:])
  return merge(left, right)

8. 기수 정렬
설명

기수 정렬( 기수 정렬)은 "버킷 정렬" 또는 빈 정렬이라고도 하는 "분포 정렬"에 속하며, 이름에서 알 수 있듯이 키 값 정보의 일부를 사용하여 "버킷"에서 정렬할 요소를 특정 항목에 배포합니다. 정렬 기능을 달성하기 위해 기수 정렬 방법은 안정적인 정렬이며 시간 복잡도는 O(nlog(r)m)입니다. 여기서 r은 취한 기수이고 m은 힙 수입니다. 때로는 기수 정렬이 더 좋습니다. 다른 안정성 정렬 방법보다 효율적입니다.

코드 구현

import math
def radix_sort(lists, radix=10):
  k = int(math.ceil(math.log(max(lists), radix)))
  bucket = [[] for i in range(radix)]
  for i in range(1, k+1):
    for j in lists:
      bucket[j/(radix**(i-1)) % (radix**i)].append(j)
    del lists[:]
    for z in bucket:
      lists += z
      del z[:]
  return lists

以上就是Python实现八大排序算法的详细介绍，希望对大家的学习有所帮助。

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