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 옷 제거제

Video Face Swap
완전히 무료인 AI 얼굴 교환 도구를 사용하여 모든 비디오의 얼굴을 쉽게 바꾸세요!

인기 기사

뜨거운 도구

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

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

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

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

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

뜨거운 주제











Linux 터미널에서 Python 버전을 보려고 할 때 Linux 터미널에서 Python 버전을 볼 때 권한 문제에 대한 솔루션 ... Python을 입력하십시오 ...

10 시간 이내에 컴퓨터 초보자 프로그래밍 기본 사항을 가르치는 방법은 무엇입니까? 컴퓨터 초보자에게 프로그래밍 지식을 가르치는 데 10 시간 밖에 걸리지 않는다면 무엇을 가르치기로 선택 하시겠습니까?

Fiddlerevery Where를 사용할 때 Man-in-the-Middle Reading에 Fiddlereverywhere를 사용할 때 감지되는 방법 ...

Python의 Pandas 라이브러리를 사용할 때는 구조가 다른 두 데이터 프레임 사이에서 전체 열을 복사하는 방법이 일반적인 문제입니다. 두 개의 dats가 있다고 가정 해

Uvicorn은 HTTP 요청을 어떻게 지속적으로 듣습니까? Uvicorn은 ASGI를 기반으로 한 가벼운 웹 서버입니다. 핵심 기능 중 하나는 HTTP 요청을 듣고 진행하는 것입니다 ...

Investing.com의 크롤링 전략 이해 많은 사람들이 종종 Investing.com (https://cn.investing.com/news/latest-news)에서 뉴스 데이터를 크롤링하려고합니다.

Linux 터미널에서 Python 사용 ...
