python算法学习之基数排序实例
基数排序法又称桶子法(bucket sort)或bin sort,顾名思义,它是透过键值的部份资讯,将要排序的元素分配至某些"桶"中,藉以达到排序的作用,基数排序法是属于稳定性的排序,其时间复杂度为O (nlog(r)m),其中r为所采取的基数,而m为堆数,在某些时候,基数排序法的效率高于其它的比较性排序法。
代码如下:
# -*- coding: utf-8 -*-
def _counting_sort(A, i):
"""计数排序,以i位进行排序,以适用于基数排序。
Args:
A (Sequence): 排序数组
i (int): 位数,从0开始而不是1
"""
C = [0] * 10 # 任意位值范围为[0,9]
A = [(a / (10 ** i) % 10, a) for a in A] # 元素i位值及其自身的元组的数组
for k, a in A:
C[k] = C[k] + 1
for i in xrange(1, 10):
C[i] = C[i] + C[i-1]
B = [0] * len(A) # 结果数组
for k, a in A[::-1]:
B[C[k]-1] = a
C[k] = C[k] - 1
return B
def radix_sort(A, d):
"""基数排序,从最低位进行排序直到最高位:
RADIX-SORT(A, d)
1 for i ← 1 to d
2 do use a stable sort to sort array A on digit i
Args:
A (Sequence): 排序数组
d (int): 最大数位数
"""
for i in xrange(d): # 遍历位数,从低到高
A = _counting_sort(A, i)
return A
def rsort(A, d):
"""基数排序(桶排序版本)"""
for i in xrange(d): # 遍历位数,从低到高
S = [[] for _ in xrange(10)] # 存放[0,9]位数值所对应元素([0-9]10个桶)
for a in A: # 遍历元素
S[a / (10 ** i) % 10].append(a) # 存放对应位数值的元素(元素当前位值在哪个桶就放进去)
A = [a for b in S for a in b] # 以当前位数值排序好的A(依次从各桶里把元素拿出来)
return A
if __name__ == '__main__':
import random, timeit
items = range(10000)
random.shuffle(items)
def test_sorted():
print(items)
sorted_items = sorted(items)
print(sorted_items)
def test_radix_sort():
print(items)
sorted_items = radix_sort(items, 4) # [0,9999],4位数
print(sorted_items)
test_methods = [test_sorted, test_radix_sort]
for test in test_methods:
name = test.__name__ # test.func_name
t = timeit.Timer(name + '()', 'from __main__ import ' + name)
print(name + ' takes time : %f' % t.timeit(1))

핫 AI 도구

Undresser.AI Undress
사실적인 누드 사진을 만들기 위한 AI 기반 앱

AI Clothes Remover
사진에서 옷을 제거하는 온라인 AI 도구입니다.

Undress AI Tool
무료로 이미지를 벗다

Clothoff.io
AI 옷 제거제

AI Hentai Generator
AI Hentai를 무료로 생성하십시오.

인기 기사

뜨거운 도구

메모장++7.3.1
사용하기 쉬운 무료 코드 편집기

SublimeText3 중국어 버전
중국어 버전, 사용하기 매우 쉽습니다.

스튜디오 13.0.1 보내기
강력한 PHP 통합 개발 환경

드림위버 CS6
시각적 웹 개발 도구

SublimeText3 Mac 버전
신 수준의 코드 편집 소프트웨어(SublimeText3)

뜨거운 주제











이 튜토리얼은 Python을 사용하여 Zipf의 법칙의 통계 개념을 처리하는 방법을 보여주고 법을 처리 할 때 Python의 읽기 및 대형 텍스트 파일을 정렬하는 효율성을 보여줍니다. ZIPF 분포라는 용어가 무엇을 의미하는지 궁금 할 것입니다. 이 용어를 이해하려면 먼저 Zipf의 법칙을 정의해야합니다. 걱정하지 마세요. 지침을 단순화하려고 노력할 것입니다. Zipf의 법칙 Zipf의 법칙은 단순히 : 큰 자연어 코퍼스에서 가장 자주 발생하는 단어는 두 번째 빈번한 단어, 세 번째 빈번한 단어보다 세 번, 네 번째 빈번한 단어 등 4 배나 자주 발생합니다. 예를 살펴 보겠습니다. 미국 영어로 브라운 코퍼스를 보면 가장 빈번한 단어는 "TH입니다.

이 기사에서는 HTML을 구문 분석하기 위해 파이썬 라이브러리 인 아름다운 수프를 사용하는 방법을 설명합니다. 데이터 추출, 다양한 HTML 구조 및 오류 처리 및 대안 (SEL과 같은 Find (), find_all (), select () 및 get_text ()와 같은 일반적인 방법을 자세히 설명합니다.

시끄러운 이미지를 다루는 것은 특히 휴대폰 또는 저해상도 카메라 사진에서 일반적인 문제입니다. 이 튜토리얼은 OpenCV를 사용 하여이 문제를 해결하기 위해 Python의 이미지 필터링 기술을 탐구합니다. 이미지 필터링 : 강력한 도구 이미지 필터

이 기사는 딥 러닝을 위해 텐서 플로와 Pytorch를 비교합니다. 데이터 준비, 모델 구축, 교육, 평가 및 배포와 관련된 단계에 대해 자세히 설명합니다. 프레임 워크, 특히 계산 포도와 관련하여 주요 차이점

데이터 과학 및 처리가 가장 좋아하는 Python은 고성능 컴퓨팅을위한 풍부한 생태계를 제공합니다. 그러나 Python의 병렬 프로그래밍은 독특한 과제를 제시합니다. 이 튜토리얼은 이러한 과제를 탐구하며 전 세계 해석에 중점을 둡니다.

이 튜토리얼은 Python 3에서 사용자 정의 파이프 라인 데이터 구조를 작성하여 클래스 및 작업자 과부하를 활용하여 향상된 기능을 보여줍니다. 파이프 라인의 유연성은 일련의 기능을 데이터 세트, GE에 적용하는 능력에 있습니다.

파이썬 객체의 직렬화 및 사막화는 사소한 프로그램의 주요 측면입니다. 무언가를 Python 파일에 저장하면 구성 파일을 읽거나 HTTP 요청에 응답하는 경우 객체 직렬화 및 사태화를 수행합니다. 어떤 의미에서, 직렬화와 사제화는 세계에서 가장 지루한 것들입니다. 이 모든 형식과 프로토콜에 대해 누가 걱정합니까? 일부 파이썬 객체를 지속하거나 스트리밍하여 나중에 완전히 검색하려고합니다. 이것은 세상을 개념적 차원에서 볼 수있는 좋은 방법입니다. 그러나 실제 수준에서 선택한 직렬화 체계, 형식 또는 프로토콜은 속도, 보안, 유지 보수 상태 및 프로그램의 기타 측면을 결정할 수 있습니다.

Python의 통계 모듈은 강력한 데이터 통계 분석 기능을 제공하여 생물 통계 및 비즈니스 분석과 같은 데이터의 전반적인 특성을 빠르게 이해할 수 있도록 도와줍니다. 데이터 포인트를 하나씩 보는 대신 평균 또는 분산과 같은 통계를보고 무시할 수있는 원래 데이터에서 트렌드와 기능을 발견하고 대형 데이터 세트를보다 쉽고 효과적으로 비교하십시오. 이 튜토리얼은 평균을 계산하고 데이터 세트의 분산 정도를 측정하는 방법을 설명합니다. 달리 명시되지 않는 한,이 모듈의 모든 함수는 단순히 평균을 합산하는 대신 평균 () 함수의 계산을 지원합니다. 부동 소수점 번호도 사용할 수 있습니다. 무작위로 가져옵니다 수입 통계 Fracti에서
