Python 데이터 구조 및 알고리즘의 일반적인 할당 정렬 방법의 예 [버킷 정렬 및 기수 정렬]_python

이 글은 주로 Python 데이터 구조와 알고리즘의 일반적인 할당 및 정렬 방법을 소개합니다. 버킷 정렬과 기수 정렬의 관련 원리와 구현 기술을 예제 형식으로 분석합니다. Python을 배워야 하는 친구들은 이 글을 참고하세요. 이 문서의 예제에서는 Python 데이터 구조 및 알고리즘의 일반적인 할당 및 정렬 방법을 설명합니다. 참고를 위해 모든 사람과 공유하세요. 세부 사항은 다음과 같습니다.

박스 정렬(버킷 정렬)

박스 정렬은 키워드 값 범위 1~m을 기준으로 하며, m개의 상자는 미리 설정되어 있습니다. 정렬에는 키워드 유형이 필요합니다. 제한된 유형이며 무한한 상자를 가질 수 있으며 실용적인 가치가 거의 없으며 일반적으로 기수 정렬의 중간 프로세스에서 사용됩니다.

버킷 정렬은 상자 정렬의 실용적인 변형으로, [0,1)과 같은 데이터 세트의 범위를 동일한 크기의 n개 하위 간격으로 나누고 각 하위 간격을 버킷으로 할당합니다. n 비레코드를 각 버킷에 넣습니다. 키워드 시퀀스가 ​​[0,1)에 고르게 분포되어 있으므로 일반적으로 동일한 버킷에 속하는 레코드가 많지 않습니다.

다음 버킷 정렬 방법은 사전을 사용하여 구현되므로 정수형의 경우 추가 공간을 만들 필요가 없습니다

def BuckSort(A):
 bucks = dict()  # 桶
 for i in A:
  bucks.setdefault(i,[]) # 每个桶默认为空列表
  bucks[i].append(i)  # 往对应的桶中添加元素
 A_sort = []
 for i in range(min(A), max(A)+1):
  if i in bucks:     # 检查是否存在对应数字的桶
   A_sort.extend(bucks[i])  # 合并桶中数据
 return A_sort

Radix sort

# 基数排序
# 输入：待排序数组s, keysize关键字位数, 亦即装箱次数, radix基数
def RadixSort(s, keysize=4, radix=10):
 # 按关键字的第k分量进行分配 k = 4,3,2,1
 def distribute(s,k):
  box = {r:[] for r in range(radix)}  # 分配用的空箱子
  for item in s:   # 依次扫描s[]，将其装箱
   t = item
   t /= 10**(k-1)
   t %= 10    # 去关键字第k位
   box[t].append(item)
  return box
 # 按分配结果重新排列数据
 def collect(s,box):
  a = 0
  for i in range(radix):
   s[a:a + len(box[i])] = box[i][:] # 将箱子中元素的合并，覆盖到原来的数组中
   a += len(box[i])     # 增加偏移值
 # 核心算法
 for k in range(1,keysize+1):
  box = distribute(s,k)   # 按基数分配
  collect(s,box)     # 按分配结果拼合

다음은 "데이터 구조 및 알고리즘 - 이론 및 실습"에서 발췌

기수 정렬은 포커 카드를 모양과 숫자로 정렬하는 것과 같이 여러 키워드로 정렬하는 것으로 확장될 수 있습니다.
일반적으로 선형 테이블에 정렬할 요소가 있다고 가정하면 각 요소에는 d 개의 키워드 {k1, k2,...,kd}가 포함되어 있으며 선형 테이블에는 선형의 두 키에 대한 정렬된 참조가 있습니다. 테이블 요소 r[i] 및 r[j], 1<=i<=j<=n은 모두 다음 순서 관계를 만족합니다.
　　{k1i,k2i,...,kdi} < ..,kdj}
k1을 최상위 숫자 키워드라고 하고, kd를 최하위 숫자 키워드라고 합니다.
정렬 방법에는 두 가지가 있습니다: 최상위 숫자 우선 MSD(최상위 숫자 우선) 및 최하위 숫자 우선 LSD(최소 유효 숫자 우선) 유효 숫자부터)

MSD: 먼저 그룹을 k1로 정렬합니다. 키워드 k1이 동일한 그룹의 요소와 동일한 경우 각 그룹을 k2로 정렬하고 하위 그룹으로 나누는 식으로 마지막 숫자 kd까지 계속합니다. 각 하위 그룹을 정렬한 다음 그룹을 연결합니다.

LSD: MSD와 달리 kd를 먼저 정렬한 다음 kd-1 등으로 정렬합니다.

PS: 다음은 참조용으로 권장되는 정렬에 대한 또 다른 데모 도구입니다.

삽입/선택/버블/병합/Hill/빠른 정렬 알고리즘 프로세스 도구의 온라인 애니메이션 데모:
http: //tools.jb51.net/aideddesign/paixu_ys

이 글의 내용은 여기까지입니다. 모든 분들께 도움이 되었으면 좋겠습니다! ! Related Related 권장 사항 :

python String 매칭 알고리즘 예제 코드

Python Crawler Entry Entry Entry Entry Entrys Entry Entryse Entry Sharing Pythoning

시

위 내용은 Python 데이터 구조 및 알고리즘의 일반적인 할당 정렬 방법의 예 [버킷 정렬 및 기수 정렬]_python의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!