python 의 기수 정렬 실현

알고리즘 사상
        삽입\교환\\선택\병합 클래스 의 정렬 알고리즘 은 모두 키워드 의 크기 를 비교 하여 정렬 을 완성 해 야 합 니 다.두 가지 비교 가 존재 하기 때문에 이러한 정렬 방법 은 가장 좋 은 상황 에서 도달 할 수 있 는 복잡 도 는 O(n*logn)입 니 다.예 를 들 어 빠 른 정렬\쌓 기 정렬\병합 정렬 등 입 니 다.일반적인 상황 과 최 악의 상황 에서 복잡 도 는 O(n**2)에 달 합 니 다.
        복잡 도 를 낮 추기 위해 소 들 이 분배 수집 정렬 방법 을 생각해 냈 다.잠시 후 시간 복잡 도 를 분석 하면 O(n)에 도달 할 수 있다.
한편,기수 정렬 은 전형 적 인 수집 분배 수집 정렬 방법 이다.기수 정렬 은 다 중 키워드 정렬 의 사상 을 빌려 단일 키워드 정렬 을 하 는 방법 이다.그 기본 사상 은 정렬 기록 을 몇 번(몇 개의 키워드 만 몇 번)'분배'와'수집'을 통 해 정렬 을 실현 하 는 것 이다.
        예:
       1.정수 순 서 를 정렬 하고 번호 0-9(10 진법 의 기수)10 개의 통 을 만들어 해당 하 는 위 치 를 번호 로 하 는 기록 에 사용 합 니 다.먼저 정렬 대기 순 서 를'개 비트'숫자 에 따라 10 개의 통 에 분배 한 다음 에 통 을 작은 것 부터 큰 것 까지 순서대로 연결 합 니 다.
        2.이전 단계 의 결 과 를'10 자리'숫자 에 따라 10 각 통 에 분배 한 다음 에 통 을 작은 것 부터 큰 것 까지 순서대로 연결 합 니 다.
        3. 지난 단계 의 결 과 를'백 자리'숫자 에 따라 10 각 통 에 분배 한 다음 통 을 작은 것 부터 큰 것 까지 순서대로 연결 합 니 다.
        4.천 자리\만 자리 가 남 았 다 면.가장 높 은 자리 의 분배 와 수집 이 완 료 될 때 까지 위 절 차 를 반복 하고 정렬 이 끝 납 니 다.
움 직 이 는 그림 예제:(초보 튜 토리 얼:1.10 기수 정렬|초보 튜 토리 얼(runoob.com)
 
알고리즘 구현
1.이 는 대기 열의 데이터 구 조 를 이용 하여 대기 열 을 정의 합 니 다.

# Bradley N. Miller, David L. Ranum
# Introduction to Data Structures and Algorithms in Python
# Copyright 2005
# 
#queue.py
 
class Queue:
    def __init__(self):
        self.items = []
 
    def isEmpty(self):
        return self.items == []
 
    def enqueue(self, item):
        self.items.insert(0,item)
 
    def dequeue(self):
        return self.items.pop()
 
    def size(self):
        return len(self.items)

2.입력 데이터 처리
하나의 목록 을 입력 으로 하고 모든 기록 을 같은 자리수 의 문자열 로 처리 합 니 다(문자열 형식 을 사용 할 때 편리 하 게 처리 합 니 다)

def inDataProcess(lis):
    max_lengh = max([len(lis[i]) for i in range(len(lis))])  #            
    return [x.zfill(max_lengh) for x in lis]  #              0           

3.기수 정렬 주 함수

def radixSort(seq:list):
    source_data = inDataProcess(seq)  #     
    res = []  #         
    big_queue = Queue()  #        
    for ele in source_data:
        big_queue.enqueue(ele)
 
    for i in range(len(source_data[0])-1,-1,-1):
        buckets = []  #         10    
        for num  in range(10):  #   10    
            bucket = Queue()
            buckets.append(bucket)
        #          
        while not big_queue.isEmpty():
            currentEle = big_queue.dequeue()  #           
            index = int(currentEle[i])  #                     
            buckets[index].enqueue(currentEle)
 
        #         
        new_big_queue = Queue()
        for bucket in buckets:
            while not bucket.isEmpty():
                out = bucket.dequeue()
                new_big_queue.enqueue(out)
                # print(new_big_queue.size())
        #   big_queue
        big_queue = new_big_queue
    #                 
    while not big_queue.isEmpty():
        res.append(big_queue.dequeue().lstrip('0'))  #   lstrip('0')    0
    return res

4.테스트 및 결과

if __name__ == '__main__':
 
    lis = [20,101,39,431,58,600,8,4,999,634,157,199,208,138,389,691,400,932,856,843,401,923]
    lis = [str(i) for i in lis]
    print(radixSort(lis))
    '''   >>>['4', '8', '20', '39', '58', '101', '138', '157', '199', '208', '389', '400', '401', '431', '600', '634', '691',
    '843', '856', '923', '932', '999']'''

알고리즘 분석
1)시간 복잡 도
n 개의 기록(모든 기록 에 d 개의 키 워드 를 포함 하고 모든 키워드 의 수치 범 위 는 rd 개 값 이 라 고 가정)에 대해 체인 기수 순 서 를 할 때 매 번 분 배 된 시간 복잡 도 는 O(n)이 고 매 번 수집 하 는 시간 복잡 도 는 O(rd)이 며 전체 순 서 는 d 번 분 배 를 하고 수집 해 야 하기 때문에 시간 복잡 도 는 O(d(n+rd)이다.
(2)공간 복잡 도
필요 한 보조 공간 은 2rd 개의 대기 열 지침 입 니 다.또한 링크 로 저장 구 조 를 해 야 하기 때문에 순서 구조 로 기록 하 는 정렬 방법 에 비해 n 개의 포인터 필드 의 공간 도 추 가 했 기 때문에 공간 복잡 도 는 O(n+rd)입 니 다.
알고리즘 특징
(1)안정 적 인 정렬 입 니 다.
(2)체인 구조 에 도 사용 할 수 있 고 순서 구조 에 도 사용 할 수 있다.
(3)시간 복잡 도 는 키워드 비교 방법 을 바탕 으로 하 는 하계 O(nlog2n)를 돌파 하여 O(n)에 도달 할 수 있다.
(4)기수 정렬 사용 조건 은 엄격 한 요구 가 있다.각급 키워드 의 주요 관계 와 각급 키워드 의 수치 범 위 를 알 아야 한다.
ref: 
1.엄 울 민 등<데이터 구조 C 언어 판(제2판)>>
2.Bradley N. Miller, David L. Ranum <>
python 의 기수 정렬 실현 에 관 한 이 글 은 여기까지 소개 되 었 습 니 다.더 많은 python 의 기수 정렬 내용 은 우리 의 이전 글 을 검색 하거나 아래 의 관련 글 을 계속 찾 아 보 세 요.앞으로 많은 응원 바 랍 니 다!